题目描述

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

输入格式

第一行输入两个整数 $n,m$，表示网格图的大小。

接下来 $n$ 行，每行输入 $m$ 个字符，表示地图 $1 ≤ n,m ≤ 100$，$1 ≤ k ≤ 9$，$1 ≤ q ≤ 7$。

输出格式

输出一行包含一个整数，表示金刚到达地心空洞入口所需要花费的最少步数。

5 5
XX13X
X.GXX
S...T
XXGXX
....2

24