/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
N \times N のマス目があります。このマス目の上から i 行目、左から j 列目を (i,j) と呼びます。
マス目の情報は N 個の文字列 S_1,S_2,\dots,S_N として与えられ、 S_i の j 文字目が . のとき (i,j) は空きマス、 # のとき (i,j) は壁マスです。
はじめ、高橋君は空きマス (N,C) におり、以下の移動を N-1 回繰り返します。
- 現在高橋君が (r,c) にいるとき、 (r-1,c-1),(r-1,c),(r-1,c+1) のいずれかを移動先として指定する。但し、マス目中に存在しないマスを移動先として指定することはできない。
- もし移動先 (a,b) が壁マスである場合、以下のことが起こる。
- 現時点で a < i \le N を満たす全ての整数について (i,b) が空きマスであった場合、 (a,b) にある壁を破壊し、移動する。すなわち、 (a,b) は空きマスになり、高橋君は (a,b) に移動する。
- そうでない場合、高橋君は移動に失敗する。この場合、移動が N-1 回に満たなくとも直ちに移動の繰り返しを終了する。
- もし移動先 (a,b) が空きマスである場合、高橋君は (a,b) に移動する。
以下の条件を満たす長さ N の文字列 R を出力してください。
- もし移動中に失敗せず (1,i) に辿り着ける場合、 R の i 文字目は
1 - そうでない場合、 R の i 文字目は
0
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- T,N,C は整数
- 1 \le T \le 50000
- 2 \le N \le 3000
- 1 \le C \le N
- S_i は
.と#からなる長さ N の文字列 - S_N の C 文字目は
. - ひとつの入力について、 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
この入力には 5 個のテストケースが含まれます。
1 番目のテストケースについて、例えば以下のようにして移動中に失敗せず (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 と出力してください。
Score : 450 points
Problem Statement
There is an N \times N grid. The cell at the i-th row from the top and j-th column from the left is called (i,j).
The grid is described by N strings S_1,S_2,\dots,S_N. If the j-th character of S_i is ., (i,j) is an empty cell; if it is #, (i,j) is a wall cell.
Initially, Takahashi-kun is at empty cell (N,C), and repeats the following movement N-1 times:
- If he is currently at (r,c), he specifies one of (r-1,c-1),(r-1,c),(r-1,c+1) as the destination. Here, he cannot specify a cell that does not exist in the grid as the destination.
- If the destination (a,b) is a wall cell, the following occurs:
- If (i,b) is currently an empty cell for all integers satisfying a < i \le N, he destroys the wall at (a,b) and moves there. That is, (a,b) becomes an empty cell and he moves to (a,b).
- Otherwise, he fails to move. In this case, he immediately ends the repetition of movements, even if he has not made N-1 movements.
- If the destination (a,b) is an empty cell, he moves to (a,b).
Output a string R of length N satisfying the following conditions:
- If he can reach (1,i) without failing during the movements, the i-th character of R is
1. - Otherwise, the i-th character of R is
0.
You are given T test cases; solve each of them.
Constraints
- T,N,C are integers.
- 1 \le T \le 50000
- 2 \le N \le 3000
- 1 \le C \le N
- S_i is a string of length N consisting of
.and#. - The C-th character of S_N is
.. - For each input, the sum of N^2 does not exceed 9 \times 10^6.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N C S_1 S_2 \vdots S_N
Output
Print T lines.
The i-th line should contain the answer for the i-th test case.
Sample Input 1
5 5 3 .###. ..#.. #.#.# #...# ##..# 2 2 ## .. 4 1 #### #### #### .### 3 3 ... ... ... 10 3 ##.##.##.# .####..#.. ...#.#..#. .#.#.#.#.. ...####... #.#.##.... .##...#... #.##.....# #....###.# .#..#.#...
Sample Output 1
10111 11 1000 111 0011010010
This input contains five test cases.
For the first test case, for example, he can reach (1,3) without failing during the movements as follows:
- Initially, he is at (5,3).
- He moves to empty cell (4,2).
- (3,3) is a wall cell, but since (4,3),(5,3) are currently both empty cells, he destroys the wall at (3,3) and moves to (3,3).
- (2,3) is a wall cell, but since (3,3),(4,3),(5,3) are currently all empty cells, he destroys the wall at (2,3) and moves to (2,3).
- (1,3) is a wall cell, but since (2,3),(3,3),(4,3),(5,3) are currently all empty cells, he destroys the wall at (1,3) and moves to (1,3).
He can reach (1,1),(1,3),(1,4),(1,5) without failing during the movements, so print 10111.