hdu 5025Saving Tang Monk（BFS）

点击打开链接

题意：从K走到T，S为怪，走的时候就多花费一秒，走到T时收集m把不同的钥匙，但是规定收集n之前，必须1~n-1全部收集完毕，怪最多有5个

思路：怪最多就有5个，然后钥匙是1~9把，我们每个点的状态就不会很多，在BFS时每个点的状态进行标记就行了，5个怪状态压缩着判断，因为这个怪在第二次经过的时候已经死了，不用花费时间去杀死它

////  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);                }            }            else                if(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");        else            PRintf("%d/n",ans);    }    return 0;}