You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给定一个大小为 N*M 的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。测试数据保证从起点一定可以移动到终点。

Input Format

第一行包含两个正整数 N 和 M 分别表示迷宫的行数和列数，接下来的 N 行，每行包含 M 个字符描述迷宫的结构用 '#'表示墙壁， '.'表示通道，'S'表示起点， 'G'表示终点。

Output Format

一个数，表示最小步数。

10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
########.#
....#.....
.####.###.
....#...G#

22

Hint

数据范围：0<N，M≤100。