分数: 366 分
问题陈述
你有一个迷宫 N \times N 网格。牢房位于 i从顶部开始的第行和 j从左边算起的第列表示为 (i, j)。每个单元格包含以下字符之一: ., #, S,或 G. . 代表一个可以通过的空单元格, # 代表一堵墙(不可通行的单元格), S 表示起始位置,并且 G 代表目标位置。细胞 S 和 G 也还过得去。
高桥想要从起始位置移动 S 到达目标位置 G。高桥可以从当前的单元格沿四个方向(上、下、左、右)之一一步移动到相邻的单元格。然而,他无法移出网格或进入墙壁牢房。
求从起始位置到目标位置(包括起始位置和目标位置)路径上的最小单元格数。
约束
- 2 \leq N \leq 500
- N 是一个整数
- 字符串 c_i (1 \leq i \leq N) 代表 i网格的第行是一个长度的字符串 N 组成
.,#,S,和G - 正好一个
S存在于整个网格中 - 正好一个
G存在于整个网格中 - 保证目标位置
G从起始位置可达S
输入
N c_1 c_2 \vdots c_N
- 第一行包含一个整数 N 代表网格的边长。
- 超过以下 N 行, i第行 (1 \leq i \leq N) 包含一个字符串 c_i 长度 N 表示中每个单元格的信息 i- 从网格顶部算起的第 3 行。的 j第一个字符 c_i 代表cell的信息 (i, j).
输出
在一行中打印访问过的最小单元格数(包括 S 和 G) 从起始位置移动时 S 到达目标位置 G.
示例输入 1
4 S... .#.. ..#G ....
示例输出 1
6
示例输入 2
3 S#. .#G ...
示例输出 2
6
示例输入 3
8 S..#.... ##.#.##. ...#...# .#####.# .....#.G .###.#.. ...#.... .#......
示例输出 3
20
示例输入 4
15 S.............. .#############. .............#. .###########.#. .#.........#.#. .#.#######.#.#. .#.#.....#.#.#. .#.#.###.#.#.#. .#.#.#G#.#.#.#. .#.#.#...#.#.#. .#.#.#####.#.#. .#.#.......#.#. .#.#########.#. .#...........#. ...............
示例输出 4
63
示例输入 5
2 SG ..
示例输出 5
2