C - 迷路の最短経路 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

N \times N のグリッド上の迷路が与えられます。上から i 行目・左から j 列目のマスを (i, j) と表します。各マスには .、#、S、G のいずれかが書かれています。. は通行可能な空きマス、# は壁（通行不可能なマス）、S はスタート地点、G はゴール地点を表します。S と G のマスも通行可能です。

高橋君はスタート地点 S からゴール地点 G まで移動したいです。高橋君は現在いるマスから上下左右に隣接するマスへ 1 手で移動できます。ただし、グリッドの外や壁のマスへは移動できません。

スタート地点からゴール地点までの経路上のマスの数（スタート地点とゴール地点を含む）の最小値を求めてください。

制約

  • 2 \leq N \leq 500
  • N は整数
  • グリッドの i 行目を表す文字列 c_i (1 \leq i \leq N) は .、#、S、G からなる長さ N の文字列である
  • S はグリッド全体でちょうど 1 つ存在する
  • G はグリッド全体でちょうど 1 つ存在する
  • スタート地点 S からゴール地点 G へ到達可能であることが保証される

入力

N
c_1
c_2
\vdots
c_N
  • 1 行目には、グリッドの一辺の大きさを表す整数 N が与えられる。
  • 続く N 行のうち i 行目 (1 \leq i \leq N) には、グリッドの上から i 行目の各マスの情報を表す長さ N の文字列 c_i が与えられる。c_i の j 文字目はマス (i, j) の情報を表す。

出力

スタート地点 S からゴール地点 G まで移動するときに通るマスの数（S と G を含む）の最小値を 1 行で出力せよ。

入力例 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

Score : 366 pts

Problem Statement

You are given a maze on an N \times N grid. The cell at the i-th row from the top and the j-th column from the left is denoted as (i, j). Each cell contains one of the following characters: ., #, S, or G. . represents a passable empty cell, # represents a wall (an impassable cell), S represents the start position, and G represents the goal position. The cells S and G are also passable.

Takahashi wants to move from the start position S to the goal position G. From his current cell, Takahashi can move in one step to an adjacent cell in one of the four directions (up, down, left, right). However, he cannot move outside the grid or into a wall cell.

Find the minimum number of cells on the path from the start position to the goal position (including the start position and the goal position).

Constraints

  • 2 \leq N \leq 500
  • N is an integer
  • The string c_i (1 \leq i \leq N) representing the i-th row of the grid is a string of length N consisting of ., #, S, and G
  • Exactly one S exists in the entire grid
  • Exactly one G exists in the entire grid
  • It is guaranteed that the goal position G is reachable from the start position S

Input

N
c_1
c_2
\vdots
c_N
  • The first line contains an integer N representing the side length of the grid.
  • Over the following N lines, the i-th line (1 \leq i \leq N) contains a string c_i of length N representing the information of each cell in the i-th row from the top of the grid. The j-th character of c_i represents the information of cell (i, j).

Output

Print in one line the minimum number of cells visited (including S and G) when moving from the start position S to the goal position G.

Sample Input 1

4
S...
.#..
..#G
....

Sample Output 1

6

Sample Input 2

3
S#.
.#G
...

Sample Output 2

6

Sample Input 3

8
S..#....
##.#.##.
...#...#
.#####.#
.....#.G
.###.#..
...#....
.#......

Sample Output 3

20

Sample Input 4

15
S..............
.#############.
.............#.
.###########.#.
.#.........#.#.
.#.#######.#.#.
.#.#.....#.#.#.
.#.#.###.#.#.#.
.#.#.#G#.#.#.#.
.#.#.#...#.#.#.
.#.#.#####.#.#.
.#.#.......#.#.
.#.#########.#.
.#...........#.
...............

Sample Output 4

63

Sample Input 5

2
SG
..

Sample Output 5

2