hdu 5025Saving Tang Monk（BFS）

//
//  main.cpp
//  dfs-bfs搜索
//
//  Created by liuzhe on 16/8/10.
//  Copyright © 2016年 my_code. All rights reserved.
//#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;const int maxn=110;
const int inf = 0x3f3f3f3f;
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 = c.x + dir[i][0];int yy = c.y + dir[i][1];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);}}elseif(str[xx][yy]=='S')//meet snake,then judge{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//时间加一，状态更新{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;cnt++;//记录怪的位置和数量}}}int ans = bfs();if(ans == inf)puts("impossible");elseprintf("%d\n",ans);}return 0;
}