四、哥斯拉大战金刚 众所周知，哥斯拉和金刚是时代仇敌，大战一触即发。金刚为了打败哥斯拉，要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个n*m的网格图，S表示金刚目前的位置，T表示地心空洞的入

四、哥斯拉大战金刚LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
众所周知，哥斯拉和金刚是时代仇敌，大战一触即发。金刚为了打败哥斯拉，要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个n*m的网格图，S表示金刚目前的位置，T表示地心空洞的入口，X表示障碍物，.表示平地。在前往地心空洞之前，金刚必须先获得一系列打开地心空洞的钥匙（在地图上通过数字1,2,…,k表示），并且获得i类钥匙的前提是金刚已经获得了1,2,…,i-1类钥匙，金刚在拿到地图上所有种类的钥匙之后即可前往地心空洞的入口。另外，同一种类的钥匙可能有多把，金刚只需获得其中任意一把即可。金刚每一步可以朝上下左右四个方向中的一个移动一格，值得注意的是，哥斯拉为了阻挠金刚的计划，还在地图上设置了q个陷阱（在网格图中用G表示），金刚第一次进入某个陷阱需要花费额外的一步来破坏陷阱（这之后该陷阱即可被视为平地）。为了更好的掌握全局，请你帮金刚计算到达地心空洞入口所需要花费的最少步数。输入数据保证有解。LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
时间限制：6000LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
内存限制：262144LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行输入两个整数n,m，表示网格图的大小。 接下来n行，每行输入m个字符，表示地图 1 ≤ n,m ≤ 100 1 ≤ k ≤ 9 1 ≤ q ≤ 7LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出一行包含一个整数，表示金刚到达地心空洞入口所需要花费的最少步数。LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例输入LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5 5LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
XX13XLAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
X.GXXLAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
S...TLAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
XXGXXLAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
....2LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例输出LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
24LAo100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库