题意：从K走到T，S为怪，走的时候就多花费一秒，走到T时收集m把不同的钥匙。可是规定收集n之前，必须1~n-1所有收集完成，怪最多有5个
思路：怪最多就有5个，然后钥匙是1~9把，我们每一个点的状态就不会非常多，在BFS时每一个点的状态进行标记即可了。5个怪状态压缩着推断，由于这个怪在第二次经过的时候已经死了，不用花费时间去杀死它
#include <map>
#include <queue>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=110;
int sx,sy,ex,ey,n,m,cnt;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int vis[maxn][maxn][10][40];
char str[maxn][maxn];
struct edge{
int x,y,step,numkey,ss;
};
struct snake{
int x,y;
}sna[10];
int bfs(){
queue<edge>que;
edge c,ne;
memset(vis,0,sizeof(vis));
c.x=sx,c.y=sy,c.step=0,c.numkey=0,c.ss=0;
vis[c.x][c.y][0][0]=1;
que.push(c);
int ans=inf;
while(!que.empty()){
c=que.front();que.pop();
if(c.x==ex&&c.y==ey&&c.numkey==m){
ans=min(ans,c.step);
}
for(int i=0;i<4;i++){
int xx=dir[i][0]+c.x;
int yy=dir[i][1]+c.y;
if(xx<0||xx>n-1||yy<0||yy>n-1||str[xx][yy]=='#') continue;
if(vis[xx][yy][c.numkey][c.ss]) continue;
ne.x=xx;ne.y=yy;ne.step=c.step+1;ne.numkey=c.numkey;ne.ss=c.ss;
if(str[xx][yy]>='1'&&str[xx][yy]<='9'){//假设走到的是钥匙的位置进行推断
int t=str[xx][yy]-'0';
if(ne.numkey==t-1){//钥匙刚好是当前钥匙数+1，就符合条件
ne.numkey++;
vis[ne.x][ne.y][ne.numkey][ne.ss]=1;
que.push(ne);
}else{//不符合直接压进队列
vis[ne.x][ne.y][ne.numkey][ne.ss]=1;
que.push(ne);
}
}else if(str[xx][yy]=='S'){//遇到怪进行推断
for(int i=0;i<cnt;i++){
if(xx==sna[i].x&&yy==sna[i].y){
if((ne.ss>>i)&1){//说明这个怪已经死掉了
vis[ne.x][ne.y][ne.numkey][ne.ss]=1;
que.push(ne);
}else{//没有死掉的话时间+1，状态更新
ne.step++;
ne.ss+=(1<<i);
vis[ne.x][ne.y][ne.numkey][ne.ss]=1;
que.push(ne);
}
break;
}
}
}else{
vis[ne.x][ne.y][ne.numkey][ne.ss]=1;
que.push(ne);
}
}
}
return ans;
}
int main(){
while(scanf("%d%d",&n,&m)!=-1){
if(n==0&&m==0) break;
cnt=0;
for(int i=0;i<n;i++) scanf("%s",str[i]);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(str[i][j]=='K')sx=i,sy=j;
if(str[i][j]=='T')ex=i,ey=j;
if(str[i][j]=='S'){
sna[cnt].x=i,
sna[cnt++].y=j;//记录怪的位置和数量
}
}
}
int ans=bfs();
if(ans==inf) puts("impossible");
else printf("%d
",ans);
}
return 0;
}