{"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 $j$\\-th character of the string $S_i$, $S_{i,j}$, means the following.\n\n*   If $S_{i,j}=$ `.`, the square $(i, j)$ is empty.\n*   If $S_{i,j}=$ `#`, the square $(i, j)$ is occupied by a white pawn, which cannot be moved or removed.\n\nWe have put a white bishop on the square $(A_x, A_y)$.  \nFind 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).  \nIf it cannot be moved to $(B_x, B_y)$, report `-1` instead.\n\n## Constraints\n\n*   $2 \\le N \\le 1500$\n*   $1 \\le A_x,A_y \\le N$\n*   $1 \\le B_x,B_y \\le N$\n*   $(A_x,A_y) \\neq (B_x,B_y)$\n*   $S_i$ is a string of length $N$ consisting of `.` and `#`.\n*   $S_{A_x,A_y}=$ `.`\n*   $S_{B_x,B_y}=$ `.`\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_x$ $A_y$\n$B_x$ $B_y$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n\n[samples]\n\n## Notes\n\nA white [bishop](https://en.wikipedia.org/wiki/Bishop_(chess)) on the square $(i, j)$ can go to the following positions in one move.\n\n*   For each positive integer $d$, it can go to $(i+d,j+d)$ if all of the conditions are satisfied.\n    *   The square $(i+d,j+d)$ exists in the board.\n    *   For every positive integer $l \\le d$, $(i+l,j+l)$ is not occupied by a white pawn.\n*   For each positive integer $d$, it can go to $(i+d,j-d)$ if all of the conditions are satisfied.\n    *   The square $(i+d,j-d)$ exists in the board.\n    *   For every positive integer $l \\le d$, $(i+l,j-l)$ is not occupied by a white pawn.\n*   For each positive integer $d$, it can go to $(i-d,j+d)$ if all of the conditions are satisfied.\n    *   The square $(i-d,j+d)$ exists in the board.\n    *   For every positive integer $l \\le d$, $(i-l,j+l)$ is not occupied by a white pawn.\n*   For each positive integer $d$, it can go to $(i-d,j-d)$ if all of the conditions are satisfied.\n    *   The square $(i-d,j-d)$ exists in the board.\n    *   For every positive integer $l \\le d$, $(i-l,j-l)$ is not occupied by a white pawn.","is_translate":false,"language":"English"}],"meta":{"iden":"abc246_e","tags":[],"sample_group":[["5\n1 3\n3 5\n....#\n...#.\n.....\n.#...\n#....","3\n\nWe can move the bishop from $(1,3)$ to $(3,5)$ in three moves as follows, but not in two or fewer moves.\n\n*   $(1,3) \\rightarrow (2,2) \\rightarrow (4,4) \\rightarrow (3,5)$"],["4\n3 2\n4 2\n....\n....\n....\n....","\\-1\n\nThere is no way to move the bishop from $(3,2)$ to $(4,2)$."],["18\n18 1\n1 18\n..................\n.####.............\n.#..#..####.......\n.####..#..#..####.\n.#..#..###...#....\n.#..#..#..#..#....\n.......####..#....\n.............####.\n..................\n..................\n.####.............\n....#..#..#.......\n.####..#..#..####.\n.#.....####..#....\n.####.....#..####.\n..........#..#..#.\n.............####.\n..................","9"]],"created_at":"2026-03-03 11:01:13"}}