Saving Tang Monk -HDU - 5025（bfs状态压缩）

题目链接：https://cn.vjudge.net/problem/HDU-5025

题解：

    注意：

        0.走一步需要一分钟，杀死蛇也需要一分钟的时间，很明显需要用优先队列来做。

        1.当某条蛇死过之后，下次再走到这条蛇的位置不用再耗费一分钟的时间打死它了。

        2.想要捡起x钥匙，必须已经捡到过1~x-1钥匙。

        3.想救出师傅必须找到所有的钥匙。

    具体思路：

        0.关于状态：此题我用了两个数组记录状态，一个数组是记录蛇的状态，另一个数组是记录钥匙的状态。在某点，若两个状态都被访问过时，此点不能走；当走到有某个钥匙x的房间时，判断钥匙数组的状态，若没有1~x-1的钥匙，则不能取走。

        1.当找到师傅时判断所有钥匙是否都已找到；

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,num;
int vis[110][110][1024];///记录钥匙状态的数组；
int book[110][110][50];///记录蛇状态的数组；
char Map[110][110];///地图；
int c[4][2]={1,0,0,1,-1,0,0,-1};///方向数组；
int Key[10]={0,1,3,7,15,31,63,127,255,511};///钥匙；

struct yun
{
    int x,y,s;
    int snake;///蛇的状态；
    int key;///钥匙的状态；
    friend bool operator < (yun a,yun b)
    {
        return a.s>b.s;
    }
};
yun st,en;

struct yu
{
    int x,y;
}Snake[5];

int bfs(int x,int y)
{
    priority_queue<yun> Q;
    st.x=x;
    st.y=y;
    st.s=0;
    st.key=0;
    st.snake=0;
    Q.push(st);
    while(Q.size())
    {
        st=Q.top();
        Q.pop();
        for(int i=0;i<4;i++)
        {
            int dx=st.x+c[i][0];
            int dy=st.y+c[i][1];
            if(dx<0||dy<0||dx>=n||dy>=n)continue;///越界；
            if(Map[dx][dy]=='#')continue;
            en.s=st.s+1;
            en.snake=st.snake;
            en.key=st.key;
            if(Map[dx][dy]=='S')///遇到蛇时；
            {
                int j;
                for(j=0;j<num;j++)
                    if(Snake[j].x==dx&&Snake[j].y==dy)///是第j条蛇；
                        break;
                int sta=1<<j;///杀死这条蛇；
                if((st.snake&sta)==0)///若这条蛇之前没遇到过；
                    en.s=st.s+2;
                en.snake=st.snake|sta;///记录状态；
            }
            else if(Map[dx][dy]>='1'&&Map[dx][dy]<='9')///遇到钥匙时；
            {
                if(st.key==Key[Map[dx][dy]-'1'])///若之前的钥匙都已拿到手；
                    en.key=Key[Map[dx][dy]-'0'];
            }
            if(vis[dx][dy][en.key]&&book[dx][dy][en.snake])///当此点的状态已访问过；
                continue;
            if(Map[dx][dy]=='T'&&st.key==Key[m])///找到师傅并拿到所有的钥匙；
                return st.s+1;
            book[dx][dy][en.snake]=1;
            vis[dx][dy][en.key]=1;
            en.x=dx;
            en.y=dy;
            Q.push(en);
        }
    }
    return -1;
}

int main()
{
    int i,j,s_x,s_y;
    while(~scanf("%d%d",&n,&m)&&(n+m))
    {
        memset(vis,0,sizeof(vis));
        memset(book,0,sizeof(book));
        num=0;
        for(i=0;i<n;i++)
        {
            scanf("%s",Map[i]);
            for(j=0;j<n;j++)
            {
                if(Map[i][j]=='K')
                {
                    s_x=i;
                    s_y=j;
                }
                if(Map[i][j]=='S')///将蛇按编号记录下来；
                {
                    Snake[num].x=i;
                    Snake[num++].y=j;
                }
            }
        }
        int ans=bfs(s_x,s_y);
        if(ans==-1)
            printf("impossible\n");
        else printf("%d\n",ans);
    }
}