DFS走迷宫
Time Limit: 1000 MSMemory Limit: 1000 KB

Description

在一个n*m的有起点和终点的二维地图中找出起点终点的最短路
‘#’、’.’、‘S’、'G’分别表示墙壁、通道、起点、终点
保证输入合法,且结果不超过int范围, 地图中一点只与上下左右4个点相邻。

Input

输入的第一行是一个int型整数T,表示一个有T组数据。
每组数据第一行包含两个数n<=100,m<=100 表示二维地图的行数,列数。
接下来有n行,表示地图。

Output

输出T行,每行一个整数,表示求得的结果。如果起点终点连通,输出exist!,否则,输出not exist!.

Sample Input

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

Sample Output

exist!
not exist!
Submit Your Code                        Discuss



苏ICP备2022026913号-1