#A0022. 第五人格!启动!

第五人格!启动!

介绍

《第五人格》是网易开发的一款非对称对抗竞技手游,核心是1对4的追逃游戏类,似于鬼抓人游戏。

背景

这天你在玩监管者,现在场地上就一个求生者了,可是地窖已经打开了,你需要最快走到地窖,而且你知道地窖点,现在你打开了右上角地图问你最快可以多久到地窖(ps:走一格用单位一的时间)

Input

第一行 输入m,n(地图尺寸m*n),m,n都小于100 第二行 输入地图:#墙壁 .通道 S当前位置 G终点也是地窖位置

给的数据没有到不了终点的

Output

一个数(最短用时)

Samples

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

Limitation

1s, 1024KiB for each test case.

你可能可以用到下面知识点