hdu5025 狀態壓縮搜索 《網絡賽題》

hdu5025 狀態壓縮搜索 《網絡賽題》

2014年網絡賽題

先說下題意 告訴你起點 終點 n*n的地圖 地圖是由空 滿 有一個標號的鑰匙 蛇組成 問能不能到達終點

你只有拿到n一下的所有鑰匙才能拿到n這把鑰匙 （比如現在要拿表號位5的鑰匙 你必須有1 2 3 4的鑰匙 如果沒有 但也能走這個格子） 但能走所有非滿的格子 蛇只能殺一次

#include
#include
#include
#include
using namespace std;

struct node
{
    int x,y,step,key;
    int kill;
}a,b;
int mark[110][110][10][50],n,m,Min,flash;//mark記錄狀態
char map[110][110];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int bfs(int starx,int stary)
{
    a.x=starx;
    a.y=stary;
    a.step=0;
    a.key=0;
    a.kill=0;
    memset(mark,127,sizeof(mark));
    mark[a.x][a.y][a.key][a.kill]=0;
    queue<node>q;
    q.push(a);
    while(!q.empty())
    {
        b=q.front();
        q.pop();
        if(map[b.x][b.y]=='T'&&b.key==m)
        {
            if(b.step<Min)
            Min=b.step;
            flash=1;
            continue;
        }
        for(int i=0;i<4;i++)
        {
            a.x=b.x+dir[i][0];
            a.y=b.y+dir[i][1];
            a.step=b.step+1;
            a.key=b.key;
            a.kill=b.kill;
            if(a.x<0||a.x>=n||a.y<0||a.y>=n) continue;
            if(map[a.x][a.y]=='#') continue;
            /*if(mark[a.x][a.y][a.key][a.kill]) continue;
            {
                if(a.step>mark[a.x][a.y][a.key][a.kill]) continue;
            }*/
            if(map[a.x][a.y]>='a'&&map[a.x][a.y]<='z')
            {
                int t=map[a.x][a.y]-'a';
                if((a.kill&(1<<t))==0)
                {
                    a.kill=a.kill|(1<<t);
                    a.step++;
                }
                //mark[a.x][a.y][a.key][a.kill]=a.step;
                //q.push(a);
            }
            else if(map[a.x][a.y]>='1'&&map[a.x][a.y]<='9')
            {
                int x=map[a.x][a.y]-'0';
                if(a.key==x-1)
                a.key=x;
                //mark[a.x][a.y][a.key][a.kill]=a.step;
                //if(a.step<=mark[a.x][a.y][a.key][a.kill]) q.push(a);
            }
            else
            {
                //mark[a.x][a.y][a.key][a.kill]=a.step;
                //q.push(a);
            }
            if(a.step<mark[a.x][a.y][a.key][a.kill])
            {
                mark[a.x][a.y][a.key][a.kill]=a.step;
                q.push(a);
            }
        }
    }
    return 0;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m),n+m)
    {
        for(i=0;i<n;i++)
        scanf("%s",map[i]);
        char t='a';
        int starx,stary,endx,endy;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(map[i][j]=='K')
                {
                    starx=i;
                    stary=j;
                }
                else if(map[i][j]=='S')
                {
                    map[i][j]=t++;
                }
                else if(map[i][j]=='T')
                {
                    endx=i;
                    endy=j;
                }
            }
        }
        Min=999999;
        flash=0;
        bfs(starx,stary);
        if(!flash) printf("impossible\n");
        else printf("%d\n",Min);
    }
    return 0;
}