HDU 胜利大逃亡(续)

胜利大逃亡(续)

Time Limit : 4000/2000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 5 Accepted Submission(s) : 4

Problem Description

Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……
这次魔王汲取了上次的教训，把Ignatius关在一个n*m的地牢里，并在地牢的某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次，若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试，Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢，如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。

Input

每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图，其中包括:
. 代表路 * 代表墙 @ 代表Ignatius的起始位置 ^ 代表地牢的出口 A-J 代表带锁的门,对应的钥匙分别为a-j a-j 代表钥匙，对应的门分别为A-J
每组测试数据之间有一个空行。

Output

针对每组测试数据，如果可以成功逃亡，请输出需要多少分钟才能离开，如果不能则输出-1。

Sample Input

4 5 17 

@A.B. 

a*.*. 

*..*^ 

c..b*
4 5 16 

@A.B. 

a*.*. 

*..*^ 

c..b*

Sample Output

16

-1

Author

Source

ACM暑期集训队练习赛（三）

用数组的第三维来标记所拿有的钥匙，最多有十把钥匙2^10中状态，也就是，走过的路还可以再走（在拿的钥匙不一样的情况下）

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=1<<11;

int n,m,t;
int mark[25][25][N];
char map[25][25];

struct node{
    int x,y,z;
    int step;
};

int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

bool judge(int x,int y){
    if(map[x][y]!='*' && x>=0 && x<m && y>=0 && y<n)
        return 1;
    return 0;
}

int BFS(int si,int sj){
    queue<node> myqueue;
    while(!myqueue.empty())
        myqueue.pop();
    node cur,next;
    cur.x=si;cur.y=sj;cur.z=0;cur.step=0;
    mark[si][sj][0]=0;
    myqueue.push(cur);
    int i,x,y,z;
    while(!myqueue.empty()){
        cur=myqueue.front();
        myqueue.pop();
        if(cur.step>=t-1)
            return -1;
        next.step=cur.step+1;
        for(i=0;i<4;i++){
            next.x=x=cur.x+dir[i][0];
            next.y=y=cur.y+dir[i][1];
            if(judge(x,y)){
                if(map[x][y]=='^')
                    return next.step;
                if(map[x][y]=='@' || map[x][y]=='.'){
                    next.z=z=cur.z;
                    if(!mark[x][y][z]){
                        mark[x][y][z]=1;
                        myqueue.push(next);
                    }
                }else if(map[x][y]>='A' && map[x][y]<='Z'){
                    next.z=z=cur.z;
                    if((z>>(map[x][y]-'A'))&1 && !mark[x][y][z]){
                        mark[x][y][z]=1;
                        myqueue.push(next);
                    }
                }else{
                    z=1<<(map[x][y]-'a');
                    next.z=z|cur.z;
                    if(!mark[x][y][next.z]){
                        mark[x][y][next.z]=1;
                        myqueue.push(next);
                    }
                }
            }
        }
    }
    return -1;
}

int main(){

    //freopen("input.txt","r",stdin);

    int i,j,x,y;
    while(scanf("%d%d%d",&m,&n,&t)!=EOF){
        memset(mark,0,sizeof(mark));
        getchar();
        for(i=0;i<m;i++){
            for(j=0;j<n;j++){
                scanf("%c",&map[i][j]);
                if(map[i][j]=='@'){
                    x=i;y=j;
                }
            }
            getchar();
        }
        int ans=BFS(x,y);
        printf("%d\n",ans);
    }
    return 0;
}