胜利大逃亡(续)(bfs＋状态hash).cpp

杭电acm解题报告2001---2099.

//关键在于状态的hash
//10把钥匙用二进制位来保存状态，状态数为2^10=1024，还有人的x，y坐标位置
#include <cstdio>
#include <memory>
#include <queue>
#include <algorithm>
#define ABS(x) ((x)<0?-(x):(x))
using namespace std;

int n,m,tt,itime;
int sx,sy,ex,ey;
char map[21][21];
int hash[1100][21][21];

struct infor
{
    short x,y;
    int it;
    int key;
    
    bool isOK()
    {
        int dis=ABS(x-ex)+ABS(y-ey);
        int ch=map[x][y];
        
        it ++;
        if(x<0 || y<0 || x>=n || y>=m || ch=='*')
            return false;
        if(ch>='A' && ch<='J')
        {
            ch -= 'A';
            if ((key & 1<<ch)==0)
                return false;
        }
        else if(ch>='a' && ch<='j')
        {
            ch -= 'a';
            key = key | 1<<ch;
        }
        if(hash[key][x][y]!=0 && hash[key][x][y]<=it)
            return false;
        if( dis+it>tt )
            return false;
        hash[key][x][y] = it;
        return true;
    }
};

queue<infor> SQ;

void bfs()
{
    infor t,now;
    
    memset(hash,0,sizeof(hash));
    
    while(!SQ.empty())
    {
        now=SQ.front();
        SQ.pop();
        
        if(now.it >= tt)    return ;
        if(now.x==ex && now.y==ey)
        {
            itime=now.it;
            return ;
        }
        
        t=now;
        t.x--;
        if(t.isOK())
            SQ.push(t);
        
        t=now;
        t.x++;
        if(t.isOK())
            SQ.push(t);
        
        t=now;
        t.y--;
        if(t.isOK())
            SQ.push(t);
        
        t=now;
        t.y++;
        if(t.isOK())
            SQ.push(t);
    }
}

int main()
{
    int i,j;
    infor t;
    
    while(scanf("%d %d %d",&n,&m,&tt)==3)
    {
        getchar();
        for(i=0;i<n;i++,getchar())
        {
            for(j=0;j<m;j++)
            {
                scanf("%c",&map[i][j]);
                if(map[i][j]=='@')
                {
                    sx=i,sy=j;
                    map[i][j]='.';
                }
                else if(map[i][j]=='^')
                {
                    ex=i,ey=j;
                    map[i][j]='.';
                }
            }
        }

        t.x=sx;t.y=sy;t.it=0;t.key=0;
        hash[0][sx][sy] = 0;
        while(!SQ.empty())
            SQ.pop();
        itime=0;
        SQ.push(t);
        bfs();
        
        if(itime!=0)
            printf("%d\n",itime);
        else
            printf("-1\n");
    }
    return 0;
}