题目描述

给定有障碍的网格图，. 为空地，# 为障碍。给定起点终点，每次移动仅可以 斜向走任意长度，问从起点到终点的最少移动次数，可能无解，无解输出 -1。

斜着走指的是：若目前在 $(x,y)$，设移动距离为 $d$，那么我们可以走到的位置分别有 $(x+d,y+d),(x+d,y-d),(x-d,y+d),(x-d,y-d)$ 这四种情况之一。但不能走出网格的边界。

输入格式

第一行输入 $N$ $A_x$ $A_y$ $B_x$ $B_y$，后四个整数分别代表起点和终点的坐标。

接下来 $N$ 行，每行输入 $N$ 个字符代表网格。

输出格式

输出一个整数代表答案

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

3

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

-1

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

9

样例 1 解释

我们可以在如下三步棋中从 $(1,3)$ 移动到 $(3,5)$ ，但不能在两步或更少的棋步中移动。

• $(1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)$

提示

• $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}=$ .