题意：给一个地图，孙悟空(K)救唐僧(T)，地图中'S'表示蛇，第一次到这要杀死蛇（蛇最多5条），多花费一分钟，'1'~'m'表示m个钥匙(m<=9)，孙悟空要依次拿到这m个钥匙，然后才能去救唐僧，集齐m个钥匙之前可以经过唐僧，集齐x个钥匙以前可以经过x+1,x+2..个钥匙，问最少多少步救到唐僧。
解法：BFS，每个节点维护四个值：
x,y ： 当前坐标
key ：已经集齐了key个钥匙
step：已经走了多少步
S ： 蛇的访问状态 (2^5的数表示，某位为1表示已经杀过了)
然后把唐僧看做钥匙m+1，再加点优化：
为了避免超时，用一个全局的dis[x][y][key][S] 表示到(x,y),已经集齐到key个钥匙，蛇的访问状态为S时的最小步数，如果BFS扩展的时候，当前状态的步数>=dis[当前状态]，那么就不再扩展下去了。
BFS中的逻辑就很简单了，看代码吧。
最后，枚举蛇的状态S，取dis[x][y][m+1][S]的最小值即为最小步数。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#define INF 0x3f3f3f3f
using namespace std;
#define N 1000007 int dis[][][][],Stot,M;
struct node
{
int x,y,key,step,S;
};
int dx[] = {,,,-};
int dy[] = {,-,,};
map<pair<int,int>,int> snake;
char ss[][];
int n,m; bool OK(int nx,int ny)
{
if(nx < n && nx >= && ny < n && ny >= && ss[nx][ny] != '#')
return true;
return false;
} void bfs(node s)
{
queue<node> que;
que.push(s);
while(!que.empty())
{
node now = que.front();
que.pop();
int nx = now.x, ny = now.y;
int key = now.key, step = now.step;
int S = now.S;
node tmp;
for(int k=;k<;k++)
{
int kx = nx + dx[k];
int ky = ny + dy[k];
if(!OK(kx,ky)) continue;
tmp.x = kx,tmp.y = ky;
if(ss[kx][ky] == 'S') //蛇
{
int ind = snake[make_pair(kx,ky)]; //是第几条蛇
tmp.key = key;
if(S & (<<(ind-))) //如果已经杀死
{
tmp.S = S;
tmp.step = step+;
}
else //否则要杀
{
tmp.S = S|(<<(ind-));
tmp.step = step+;
}
if(tmp.step < dis[kx][ky][tmp.key][tmp.S])
{
dis[kx][ky][tmp.key][tmp.S] = tmp.step;
que.push(tmp);
}
}
else if(ss[kx][ky] >= '' && ss[kx][ky] <= '') //钥匙点
{
int num = ss[kx][ky] - '';
tmp.step = step+;
tmp.S = S;
if(num == key+) //正好是要拿的那个
tmp.key = key+;
else
tmp.key = key;
if(tmp.step < dis[kx][ky][tmp.key][tmp.S])
{
dis[kx][ky][tmp.key][tmp.S] = tmp.step;
que.push(tmp);
}
}
else if(ss[kx][ky] == '$') //唐僧这个点
{
tmp.key = key;
tmp.S = S;
tmp.step = step+;
if(M == key+) //已经集齐了所有钥匙，不再扩展，更新dis即可
dis[kx][ky][M][S] = min(dis[kx][ky][M][S],step+);
else //没有集齐，继续走
que.push(tmp);
}
else if(ss[kx][ky] == '.')
{
tmp.key = key;
tmp.S = S;
tmp.step = step+;
if(tmp.step < dis[kx][ky][tmp.key][tmp.S])
{
dis[kx][ky][tmp.key][tmp.S] = tmp.step;
que.push(tmp);
}
}
}
}
} int main()
{
int Sx,Ex,Sy,Ey;
int i,j;
while(scanf("%d%d",&n,&m)!=EOF && n+m)
{
if(n == )
{
puts("impossible");
continue;
}
snake.clear();
Stot = ;
M = m+;
for(i=;i<n;i++)
{
scanf("%s",ss[i]);
for(j=;j<n;j++)
{
if(ss[i][j] == 'K')
Sx = i,Sy = j, ss[i][j] = '.';
else if(ss[i][j] == 'T')
Ex = i,Ey = j, ss[i][j] = '$';
else if(ss[i][j] == 'S')
snake[make_pair(i,j)] = ++Stot;
}
}
node tmp;
tmp.x = Sx,tmp.y = Sy,tmp.key = ,tmp.step = ,tmp.S = ;
memset(dis,INF,sizeof(dis));
dis[Sx][Sy][][] = ;
bfs(tmp);
int mini = INF;
for(i=;i<(<<Stot);i++)
mini = min(mini,dis[Ex][Ey][M][i]);
if(mini == INF)
puts("impossible");
else
printf("%d\n",mini);
}
return ;
}