题目描述

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

输入格式

第一行为 $N(1\le N\le 1500)$，表示网格图的行列数。

第二行为起点的行列号。

第三行为终点的行列号。

后面 $N$ 行为网格图。

输出格式

起点到终点的最少移动次数，可能无解，无解输出 -1。

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

3

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

-1

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

9