胜利大逃亡(续)

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 8029 Accepted Submission(s): 2865

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  

题目大意：给你一张（n*m）地图，在地图中‘@’为你的起始位置，‘^’为目标即你需要到达的位置，‘*’为墙，不可走的点，‘.’为空地，你可以走的点，小写字母为钥匙，大写字母为门，要打开门必须要拥有对应小写字母的钥匙才能打开，现在给你一个时间限定，你必须在ts之前（不能等于）并且以最快的时间从起点找到目标位置，开始时间为0，每移动一格为1s，如果能找到，输出最少的时间，否则输出-1

题目思路：开始看到题目时首先想到的是bfs求最短的时间到达，但是关键在于：中间找到钥匙要存起来，遇到要检测是否拥有钥匙，这个还好处理，关键在于你找到钥匙后就可以返回走，也就是你之前标记过走过的点又可以继续走，而且仅限于状态改变的节点，所以就去看了别人的思路，，其中一个很重要的标记方法，用一个三维数组

v[30][30][1025] 来标记，其中第三维表示每个点都有1024种状态，因为有十把钥匙，用十位二进制表示，这样就解决了如何判断当前点这个状态可不可以走。然后接下来处理存钥匙和检测钥匙开门，十把钥匙可以用十位二进制表示，1表示有改钥匙，0表示没有改钥匙，字母a,b,c,d,,,,,分别代表第1,2,3,4，，，把钥匙，即第一把钥匙表示为 1 第二把 10 第三把 100 第四把 1000 ..... 所以第i把钥匙可以表示为 1<<i ，存钥匙用到的是或运算，有1就为1没有就为0 所以存第i把钥匙为（key为当前钥匙的状态） key=key|(1<<i), 取钥匙是与运算取第i把钥匙为 key&(1<<i) 值为 1表示有钥匙，0位没有钥匙所以接下来就是bfs模板！！！

AC代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

int vis[25][25][1025]; //每个点都有1<<10种状态
char map[25][25];
int fx[4][2]={1,0,-1,0,0,1,0,-1};
int n,m,t;

struct nod{
    int time,key,x,y;
};
queue<nod>q;
int bfs(){
    nod next,temp;
    while(!q.empty()){
        temp=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            next.time=temp.time;
            next.key=temp.key;
            int h=fx[i][0]+temp.x;
            int l=fx[i][1]+temp.y;
            if(h>=0&&h<n&&l>=0&&l<m&&map[h][l]!='*'){
                next.time++;
                next.x=h;
                next.y=l;
                if(map[h][l]>='A'&&map[h][l]<='J'){
                    int aa=1<<(map[h][l]-'A');  //开门
                    if(next.key&aa&&!vis[h][l][next.key]){
                        vis[h][l][next.key]=1;
                        q.push(next);
                    }
                }
                    else if(map[h][l]>='a'&&map[h][l]<='j'){
                        int aa=1<<(map[h][l]-'a');
                        next.key|=aa;       //装钥匙
                        if(!vis[h][l][next.key]){
                            vis[h][l][next.key]=1;
                           q.push(next);
                        }
                    }
                    else if(!vis[h][l][next.key]){
                        vis[h][l][next.key]=1;   //改状态下没有走过的点
                        q.push(next);
                    }
                    if(map[h][l]=='^'){
                        if(next.time<t)return next.time;   //找到了钥匙
                        else return -1;
                    }
                }
            }
        }
     return -1;
}


int main()
{
   while(cin>>n>>m>>t){
        while(!q.empty())q.pop();
        memset(vis,0,sizeof(vis));
        int s,t;
    for(int i=0;i<n;i++){
        scanf("%s",map[i]);
        for(int j=0;j<m;j++)
            if(map[i][j]=='@')s=i,t=j;
    }
    nod st;
    st.key=0;
    st.time=0;
    st.x=s;
    st.y=t;
    q.push(st); //起始节点
    cout<<bfs()<<endl;
   }
   return 0;
}

HDU-1429（胜利大逃亡续）-BFS+状态压缩

胜利大逃亡(续)