分数: 450 点
问题陈述
有一个 N \times N 网格。牢房位于 i从顶部开始的第行和 j从左边算起的第列称为 (i,j).
网格描述为 N 字符串 S_1,S_2,\dots,S_N。如果 j- 第一个字符 S_i is ., (i,j) 是一个空单元格;如果是的话 #, (i,j) 是壁细胞。
最初,高桥君在空牢房里 (N,C),并重复以下动作 N-1 次:
- 如果他目前在 (r,c),他指定其中之一 (r-1,c-1),(r-1,c),(r-1,c+1) 作为目的地。在这里,他无法指定网格中不存在的单元格作为目的地。
- 如果目的地 (a,b) 是壁细胞,会发生以下情况:
- If (i,b) 当前是一个空单元格,适用于满足以下条件的所有整数 a < i \le N,他摧毁了墙 (a,b) 并移至那里。也就是说, (a,b) 变成一个空单元格,他移动到 (a,b).
- 否则,他无法移动。在这种情况下,他会立即结束动作的重复,即使他还没有做出任何动作。 N-1 动作。
- 如果目的地 (a,b) 是一个空单元格,他移动到 (a,b).
输出字符串 R 长度 N 满足以下条件:
- 如果他能到达 (1,i) 在运动过程中没有失败, i- 第一个字符 R is
1. - 否则, i- 第一个字符 R is
0.
你被给予 T 测试用例;解决它们中的每一个。
约束
- T,N,C 是整数。
- 1 \le T \le 50000
- 2 \le N \le 3000
- 1 \le C \le N
- S_i 是一个长度为的字符串 N 组成
.和#. - 的 C- 第一个字符 S_N is
.. - 对于每个输入,总和 N^2 不超过 9 \times 10^6.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N C S_1 S_2 \vdots S_N
输出
打印 T 行。
的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
5 5 3 .###. ..#.. #.#.# #...# ##..# 2 2 ## .. 4 1 #### #### #### .### 3 3 ... ... ... 10 3 ##.##.##.# .####..#.. ...#.#..#. .#.#.#.#.. ...####... #.#.##.... .##...#... #.##.....# #....###.# .#..#.#...
示例输出 1
10111 11 1000 111 0011010010
此输入包含五个测试用例。
例如,对于第一个测试用例,他可以达到 (1,3) 在以下运动过程中不会失败:
- 最初,他位于 (5,3).
- 他移至空单元格 (4,2).
- (3,3) 是一个壁细胞,但由于 (4,3),(5,3) 目前都是空牢房,他摧毁了墙壁 (3,3) 并移至 (3,3).
- (2,3) 是一个壁细胞,但由于 (3,3),(4,3),(5,3) 目前所有单元格都是空的,他摧毁了墙壁 (2,3) 并移至 (2,3).
- (1,3) 是一个壁细胞,但由于 (2,3),(3,3),(4,3),(5,3) 目前所有单元格都是空的,他摧毁了墙壁 (1,3) 并移至 (1,3).
他可以达到 (1,1),(1,3),(1,4),(1,5) 在运动过程中没有失败,所以打印 10111.