/ 
Time Limit: 6 sec / Memory Limit: 2048 MB
配点 : 500 点
問題文
ここに、 N \times N のチェス盤があります。このチェス盤の上から i 行目、左から j 列目にあるマスをマス (i,j) と呼びます。
チェス盤の情報は N 個の文字列 S_i として与えられます。
文字列 S_i の j 文字目である S_{i,j} には、以下の情報が含まれています。
- S_{i,j}=
.のとき マス (i,j) には何も置かれていない。 - S_{i,j}=
#のとき マス (i,j) には白のポーンが 1 つ置かれている。このポーンを動かしたり取り除いたりすることはできない。
この盤面のマス (A_x,A_y) に、白のビショップを 1 つ置きました。
この白のビショップをチェスのルール (注記参照) に従ってマス (A_x,A_y) からマス (B_x,B_y) に移動させるために必要な最小の手数を求めてください。
ただし、移動できない場合は代わりに -1 を出力してください。
注記
マス (i,j) に置かれている白の ビショップ は、 1 手で以下のルールに従って移動することができます。
-
各正整数 d について、以下の条件を全て満たせばマス (i+d,j+d) に移動できる。
- マス (i+d,j+d) が盤内に存在する
- 全ての正整数 l \le d について、 (i+l,j+l) に白のポーンがない
-
各正整数 d について、以下の条件を全て満たせばマス (i+d,j-d) に移動できる。
- マス (i+d,j-d) が盤内に存在する
- 全ての正整数 l \le d について、 (i+l,j-l) に白のポーンがない
-
各正整数 d について、以下の条件を全て満たせばマス (i-d,j+d) に移動できる。
- マス (i-d,j+d) が盤内に存在する
- 全ての正整数 l \le d について、 (i-l,j+l) に白のポーンがない
-
各正整数 d について、以下の条件を全て満たせばマス (i-d,j-d) に移動できる。
- マス (i-d,j-d) が盤内に存在する
- 全ての正整数 l \le d について、 (i-l,j-l) に白のポーンがない
制約
- 2 \le N \le 1500
- 1 \le A_x,A_y \le N
- 1 \le B_x,B_y \le N
- (A_x,A_y) \neq (B_x,B_y)
- S_i は
.および#からなる N 文字の文字列 - S_{A_x,A_y}=
. - S_{B_x,B_y}=
.
入力
入力は以下の形式で標準入力から与えられる。
N A_x A_y B_x B_y S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
5 1 3 3 5 ....# ...#. ..... .#... #....
出力例 1
3
以下のように移動させることで 3 手でビショップを (1,3) から (3,5) まで移動させることができます。 2 手以内でビショップを (1,3) から (3,5) まで移動させることはできません。
- (1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)
入力例 2
4 3 2 4 2 .... .... .... ....
出力例 2
-1
どのようにビショップを動かしても (3,2) から (4,2) に移動させることはできません。
入力例 3
18 18 1 1 18 .................. .####............. .#..#..####....... .####..#..#..####. .#..#..###...#.... .#..#..#..#..#.... .......####..#.... .............####. .................. .................. .####............. ....#..#..#....... .####..#..#..####. .#.....####..#.... .####.....#..####. ..........#..#..#. .............####. ..................
出力例 3
9
Score : 500 points
Problem Statement
We have an N \times N chessboard. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of this board.
The board is described by N strings S_i.
The j-th character of the string S_i, S_{i,j}, means the following.
- If S_{i,j}=
., the square (i, j) is empty. - If S_{i,j}=
#, the square (i, j) is occupied by a white pawn, which cannot be moved or removed.
We have put a white bishop on the square (A_x, A_y).
Find the minimum number of moves needed to move this bishop from (A_x, A_y) to (B_x, B_y) according to the rules of chess (see Notes).
If it cannot be moved to (B_x, B_y), report -1 instead.
Notes
A white bishop on the square (i, j) can go to the following positions in one move.
-
For each positive integer d, it can go to (i+d,j+d) if all of the conditions are satisfied.
- The square (i+d,j+d) exists in the board.
- For every positive integer l \le d, (i+l,j+l) is not occupied by a white pawn.
-
For each positive integer d, it can go to (i+d,j-d) if all of the conditions are satisfied.
- The square (i+d,j-d) exists in the board.
- For every positive integer l \le d, (i+l,j-l) is not occupied by a white pawn.
-
For each positive integer d, it can go to (i-d,j+d) if all of the conditions are satisfied.
- The square (i-d,j+d) exists in the board.
- For every positive integer l \le d, (i-l,j+l) is not occupied by a white pawn.
-
For each positive integer d, it can go to (i-d,j-d) if all of the conditions are satisfied.
- The square (i-d,j-d) exists in the board.
- For every positive integer l \le d, (i-l,j-l) is not occupied by a white pawn.
Constraints
- 2 \le N \le 1500
- 1 \le A_x,A_y \le N
- 1 \le B_x,B_y \le N
- (A_x,A_y) \neq (B_x,B_y)
- S_i is a string of length N consisting of
.and#. - S_{A_x,A_y}=
. - S_{B_x,B_y}=
.
Input
Input is given from Standard Input in the following format:
N A_x A_y B_x B_y S_1 S_2 \vdots S_N
Output
Print the answer.
Sample Input 1
5 1 3 3 5 ....# ...#. ..... .#... #....
Sample Output 1
3
We can move the bishop from (1,3) to (3,5) in three moves as follows, but not in two or fewer moves.
- (1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)
Sample Input 2
4 3 2 4 2 .... .... .... ....
Sample Output 2
-1
There is no way to move the bishop from (3,2) to (4,2).
Sample Input 3
18 18 1 1 18 .................. .####............. .#..#..####....... .####..#..#..####. .#..#..###...#.... .#..#..#..#..#.... .......####..#.... .............####. .................. .................. .####............. ....#..#..#....... .####..#..#..####. .#.....####..#.... .####.....#..####. ..........#..#..#. .............####. ..................
Sample Output 3
9