/*
这是我做过的一道新类型的搜索题!从来没想过用四维数组记录状态!
以前做过的都是用二维的!自己的四维还是太狭隘了..... 题意:悟空救师傅 ! 在救师父之前要先把所有的钥匙找到!
每种钥匙有 k 种, 每一种有多个! 只要求找到每一种的其中一个就可以!
找钥匙的顺序按照 第1种, 第2种, 第3种 ....第k种!
找钥匙的时间是一步, 走到相邻空地的时间是一步, 打蛇的时间就是两步!
求找到师傅的最少步数! 这里说一下 state[N][N][10][35]表示的含义: ->state[x][y][i][j]
前两维就不用说了,就是地图上的坐标, 第三维表示的是当前找到第几把钥匙
第四维表示的沿着一条路径走到 (x, y)找到 第 i 把钥匙打掉了哪几条蛇!
将 j 拆分成 二进制, 从右往左数, 如果第 k 为是1, 表示第 k 条 蛇杀掉了!
*/ #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue> #define N 105
using namespace std; char mp[][]; bool state[N][N][][]; int bx, by; struct node{
int x, y;
int numk, snk;
int step;
node(){} node(int x, int y, int numk, int snk, int step){
this->x = x;
this->y = y;
this->numk = numk;
this->snk = snk;
this->step = step;
}
}; int n, m;
int dir[][] = {, , , , -, , , -};
bool operator < (node a, node b) {
return a.step > b.step;
} priority_queue<node>q; bool bfs(){
while(!q.empty()) q.pop();
memset(state, false, sizeof(state));
q.push( node(bx, by, , , ) );
state[bx][by][][] = true;
while( !q.empty() ) {
node cur = q.top();
q.pop();
for(int i=; i<; ++i){
int x = cur.x + dir[i][];
int y = cur.y + dir[i][];
if(x< || x>n || y< || y>n || mp[x][y]=='#') continue;
int numk = cur.numk, snk = cur.snk, step = cur.step;
if(mp[x][y] == '.')
step += ;
else if( mp[x][y] >= '' && mp[x][y] <= ''){
if( numk + == mp[x][y] - '' )
numk += ;
step += ;
}
else if( mp[x][y] >= 'A' && mp[x][y] <= 'E' ){//这一步是关键
int cnt = mp[x][y] - 'A' + ;
if( ( << (cnt-) ) & snk ) step += ;//如果这一条蛇已经被打过了,也就是一条路又折回到这一个点
else{//在这一条路上,这条蛇没有被打过,那就将它打掉,并标记这条蛇打过了!
step += ;
snk ^= ( << (cnt-) );
}
}
else if( mp[x][y] == 'T' && numk == m ){
printf("%d\n", step + );
return true;
}
else step += ; if( state[x][y][numk][snk] ) continue;
state[x][y][numk][snk] = true;
q.push( node(x, y, numk, snk, step) );
}
}
return false;
} int main(){
while( scanf("%d%d", &n, &m) && (n ||m) ) {
int cntS = ;
for(int i = ; i <= n; ++ i){
scanf("%s", mp[i] + );
for(int j = ; j <=n; ++ j)
if(mp[i][j] == 'K'){
bx = i;
by = j;
}
else if(mp[i][j] == 'S')
mp[i][j] = 'A' + cntS++;
}
if( !bfs() ) printf("impossible\n");
}
return ;
}