Bishop 2

AtCoder

IDabc246_e

Time6000ms

Memory256MB

Difficulty—

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. ## 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$ [samples] ## Notes A white [bishop](https://en.wikipedia.org/wiki/Bishop_(chess)) 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.

Samples

Input #1

5
1 3
3 5
....#
...#.
.....
.#...
#....

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)$

Input #2

4
3 2
4 2
....
....
....
....

Output #2

\-1

There is no way to move the bishop from $(3,2)$ to $(4,2)$.

Input #3

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Bishop 2",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc246_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.  \nThe board is described by $N$ strings $S_i$.  \nThe ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments