众所周知,哥斯拉和金刚是时代仇敌,大战一触即发。金刚为了打败哥斯拉,要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个n*m的网格图,S表示金刚目前的位置,T表示地心空洞的入口,X表示障碍物,.表示平地。在前往地心空洞之前,金刚必须先获得一系列打开地心空洞的钥匙(在地图上通过数字1,2,…,k表示),并且获得i类钥匙的前提是金刚已经获得了1,2,…,i-1类钥匙,金刚在拿到地图上所有种类的钥匙之后即可前往地心空洞的入口。另外,同一种类的钥匙可能有多把,金刚只需获得其中任意一把即可。金刚每一步可以朝上下左右四个方向中的一个移动一格,值得注意的是,哥斯拉为了阻挠金刚的计划,还在地图上设置了q个陷阱(在网格图中用G表示),金刚第一次进入某个陷阱需要花费额外的一步来破坏陷阱(这之后该陷阱即可被视为平地)。为了更好的掌握全局,请你帮金刚计算到达地心空洞入口所需要花费的最少步数。输入数据保证有解。