E - Bishop 2 Editorial /

Time Limit: 6 sec / Memory Limit: 2048 MB

配点 : 500

問題文

ここに、 N \times N のチェス盤があります。このチェス盤の上から i 行目、左から j 列目にあるマスをマス (i,j) と呼びます。
チェス盤の情報は N 個の文字列 S_i として与えられます。
文字列 S_ij 文字目である 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