← 返回题目列表

AtCoder · awc0084_c

C. 迷宫中的最短路径

中文机器翻译题面 查看原题

分数: 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