第一次写带状态压缩的BFS。
因为钥匙要按次序拿到，所以直接按1--k取就可以了，如果没有次序要求，可以直接用二进制数表示。
为了取钥匙，会走回原先经过的点，但是对应的钥匙状态不一样，所以用四维数组判重就可以了。
kill snake之后可能还会走到原先的格子（只要钥匙数目不同，状态就不同，就可以再次经过，所以可以用二进制数表示all snake的状态。
这里面为了找钥匙会反复往回走，所以第一次找到的结果不一定是最短路，需要枚举所有的path。
本地debug了好久。。。是因为少push了访问过的S
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
using namespace std;
//hdu 5025
int N;
int M;
const int maxn=110;
int f[maxn][maxn][10][1<<5];
bool used[maxn][maxn][10][1<<5];
char mp[maxn][maxn];
pair<int,int>st;
pair<int,int>ed;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int ans;
int cnt;
struct node
{
int x;
int y;
int key;//how many keys have got
int snake;//the status of snakes, which is a binary number
node()
{
x=y=key=snake=0;
}
node(int xx,int yy,int kk,int ss)
{
x=xx;
y=yy;
key=kk;
snake=ss;
}
};
void bfs()
{
ans=0x3f3f3f3f;
memset(f,0,sizeof(f));
memset(used,false,sizeof(used));
queue<node>q;
q.push(node(st.first,st.second,0,0));
while(!q.empty())
{
node tmp=q.front();
q.pop();
used[tmp.x][tmp.y][tmp.key][tmp.snake]=true;
// cout<<tmp.x<<" "<<tmp.y<<" "<<mp[tmp.x][tmp.y]<<" "<<tmp.key<<" "<<hex<<tmp.snake<<" "<<f[tmp.x][tmp.y][tmp.key][tmp.snake]<<endl;
//cout<<tmp.x<<" "<<tmp.y<<endl;
if(tmp.key==M&&tmp.x==ed.first&&tmp.y==ed.second)
{
ans=min(ans,f[tmp.x][tmp.y][tmp.key][tmp.snake]);//因为此处需要返回去那钥匙，不同于一般的BFS，最先所以找到的路径不一定是最短路。
// ans=f[tmp.x][tmp.y][tmp.key][tmp.snake];
//break;
}
for(int i=0;i<4;i++)
{
int x=tmp.x+dx[i];
int y=tmp.y+dy[i];
int k=tmp.key;//当前已有第k个钥匙，下一个要拿No. k+1
int s=tmp.snake;
if(used[x][y][k][s]) continue;
if(x<0||x>=N||y<0||y>=N) continue;
// cout<<x<<" "<<y<<" "<<k<<" "<<s<<endl;
if(mp[x][y]=='0'+k+1)
{
// cout<<x<<" a "<<y<<" "<<mp[x][y]<<endl;
f[x][y][k+1][s]=f[tmp.x][tmp.y][k][s]+1;
q.push(node(x,y,k+1,s));
used[x][y][k+1][s]=true;
continue;
}
else if(mp[x][y]>='A'&&mp[x][y]<'A'+cnt)
{
// cout<<x<<" b "<<y<<" "<<mp[x][y]<<endl;
int t=mp[x][y]-'A';
// cout<<(s&(1<<t))<<endl;
if((s&(1<<t))==0) //don't forget ()!
{
// cout<<f[tmp.x][tmp.y][k][s]<<endl;
f[x][y][k][s|(1<<t)]=f[tmp.x][tmp.y][k][s]+2;
q.push(node(x,y,k,s|(1<<t)));
used[x][y][k][s|(1<<t)]=true;
}
else
{
f[x][y][k][s|(1<<t)]=f[tmp.x][tmp.y][k][s]+1;
q.push(node(x,y,k,s|(1<<t)));
used[x][y][k][s|(1<<t)]=true;
}
continue;
}
else if(mp[x][y]!='#')//mp[x][y]=='.'||mp[x][y]=='K'||mp[x][y]=='T'
{
// cout<<x<<" c "<<y<<" "<<mp[x][y]<<endl;
f[x][y][k][s]=f[tmp.x][tmp.y][k][s]+1;
q.push(node(x,y,k,s));
used[x][y][k][s]=true;
continue;
}
}
}
}
int main()
{
freopen("input.txt","r",stdin);
// freopen("data.txt","r",stdin);
// freopen("out1.txt","w",stdout);
while(true)
{
scanf("%d %d",&N,&M);
if(N==0&&M==0) break;
else
{
cnt=0;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
char a;
cin>>a;
if(a=='K')
{
st.first=i;
st.second=j;
}
else if(a=='T')
{
ed.first=i;
ed.second=j;
}
else if(a=='S')
{
a='A'+cnt;
cnt++;
}
mp[i][j]=a;
}
}
bfs();
if(ans==0x3f3f3f3f)
{
printf("impossible\n");
}
else
{
printf("%d\n",ans);
}
}
}
return 0;
}