hdu 1429（BFS+状态压缩）

胜利大逃亡(续)

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8379 Accepted Submission(s): 3008

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暑期集训队练习赛（三）

这个看了别人的代码发现还可以这样写

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<map>
  8 #include<set>
  9 #include<vector>
 10 #include<cstdlib>
 11 #include<string>
 12 #include<stack>
 13 #define eps 0.000000001
 14 typedef long long ll;
 15 typedef unsigned long long LL;
 16 using namespace std;
 17 const int N=100+10;
 18 char mp[N][N];
 19 int _x[4]={0,1,0,-1};
 20 int _y[4]={1,0,-1,0};
 21 int vis[21][21][1030];
 22 int pow2[25];
 23 int n,m,t;
 24 struct node{
 25     int x,y;
 26     int step,k;
 27 };
 28 void init()
 29 {
 30     pow2[0]=1;
 31     for(int i=1;i<=24;i++)
 32         pow2[i]=1<<i;
 33 }
 34 bool judge(int x,int y,int k)
 35 {
 36     if(x<0||y<0||x>=n||y>=m||mp[x][y]=='*')
 37         return false;
 38     if(vis[x][y][k])return false;
 39     return true;
 40 }
 41 int BFS(int x,int y)
 42 {
 43     queue<node>q;
 44     node first,next;
 45     first.x=x;first.y=y;
 46     first.step=first.k=0;
 47     q.push(first);
 48     vis[x][y][0]=1;
 49     while(!q.empty()) {
 50         //cout<<2<<endl;
 51         next=q.front();
 52         q.pop();
 53         for(int i=0;i<4;i++) {
 54             int xx=next.x+_x[i];
 55             int yy=next.y+_y[i];
 56             if(judge(xx,yy,next.k)){
 57                 if(mp[xx][yy]=='^')
 58                     return next.step+1;
 59                 first.x=xx;
 60                 first.y=yy;
 61                 first.step=next.step;
 62                 first.k=next.k;
 63                 if(mp[xx][yy]>='A'&&mp[xx][yy]<='J') {
 64                     int c=mp[xx][yy]-'A';
 65                     if(first.k&pow2[c]){
 66                         vis[xx][yy][first.k]=1;
 67                         first.step+=1;
 68                         q.push(first);
 69                     }
 70                 }
 71                 else if(mp[xx][yy]>='a'&&mp[xx][yy]<='j') {
 72                     int c = mp[xx][yy]-'a';
 73                     if(!vis[xx][yy][first.k|pow2[c]]){
 74                         first.k=first.k|pow2[c];
 75                         vis[xx][yy][first.k]=1;
 76                         first.step+=1;
 77                         q.push(first);
 78                     }
 79                 }
 80                 else if(mp[xx][yy]=='.'||mp[xx][yy]=='@') {
 81                     vis[xx][yy][first.k]=1;
 82                     first.step+=1;
 83                     q.push(first);
 84                 }
 85             }
 86         }
 87     }
 88     return -1;
 89 }
 90 int main(){
 91     //getchar();
 92     init();
 93     while(scanf("%d%d%d",&n,&m,&t)!=EOF){
 94         memset(vis,0,sizeof(vis));
 95         for(int i=0;i<n;i++)
 96             scanf("%s",mp[i]);
 97         int x,y;
 98         for(int i=0;i<n;i++) 
 99         for(int j=0;j<m;j++) {
100             if(mp[i][j]=='@'){
101                     x=i;
102                     y=j;
103             }
104         }
105          int ans=BFS(x,y);
106          if(ans==-1||ans>= t)
107             cout<<-1<<endl;
108          else
109            cout<<ans<<endl;
110     }
111 }