← 返回题目列表

AtCoder · abc443_e

E. 攀爬银

中文机器翻译题面 查看原题

分数: 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.