/ 
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 500 点
コンテスト開催当時はメモリ制限が2GBでしたが、ジャッジ環境が異なるため、現在はメモリ制限を1GBに設定しております。なお、このメモリ制限でもAC出来ることは確認しています。
問題文
ここに、 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
During the time of the contest, the memory limit was set to 2GB. However, due to a change in the judging environment, the memory limit has now been set to 1GB. Please note that it has been confirmed that solutions can still achieve an Acceptable Completion (AC) within this memory limit.
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