【入力例】
10
10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
【出力例】
22
import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static final int INF = 100000000;
static final int dx[] = {1, 0, -1, 0};
static final int dy[] = {0, 1, 0, -1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int MAX_N = N;
int MAX_M = M;
char maze[][] = new char[MAX_N][MAX_M];
for (int i=0; i<MAX_N; i++) {
maze[i] = sc.next().toCharArray();
System.out.println(maze[i]);
}
int sx=0, sy=0, gx=0, gy = 0;
for (int i=0; i<MAX_N; i++) {
for (int j=0; j<MAX_M; j++) {
if (maze[i][j] == 'S') {
sx = j;
sy = i;
} else if (maze[i][j] == 'G') {
gx = j;
gy = i;
}
}
}
int d[][] = new int[MAX_N][MAX_M];
solve(N, M, d, sx, sy, gx, gy, maze);
}
static int bfs(int N, int M, int d[][], int sx, int sy, int gx, int gy, char[][] maze) {
Queue<SimpleEntry<Integer, Integer>> que = new ArrayDeque<>();
SimpleEntry<Integer, Integer> p = new SimpleEntry<>(sy, sx);
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
d[i][j] = INF;
}
}
que.add(p);
d[sy][sx] = 0;
while (que.size() != 0) {
p = que.poll();
if (p.getKey() == gy && p.getValue() == gx) break;
for (int i=0; i<4; i++) {
int nx = p.getValue() + dx[i], ny = p.getKey() + dy[i];
if (0 <= nx && nx < N && 0 <= ny && ny < M && maze[ny][nx] != '#' && d[ny][nx] == INF) {
d[ny][nx] = d[p.getKey()][p.getValue()] + 1;
SimpleEntry<Integer, Integer> r = new SimpleEntry<>(ny, nx);
que.add(r);
}
}
}
return d[gy][gx];
}
static void solve(int N, int M, int[][]d, int sx, int sy, int gx, int gy, char maze[][]) {
int res = bfs(N, M, d, sx, sy, gx, gy, maze);
System.out.println(res);
}
}