hdu 1885(状态压缩+bfs)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1885
思路：对于钥匙，才4把，直接状态压缩搞一下就好了，然后就是开个三位数组标记状态了，跟普通bfs没什么区别。
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 #define MAXN 110
 8 struct Node{
 9     int x,y,step;
10     int key;
11 };
12 char map[MAXN][MAXN];
13 bool mark[MAXN][MAXN][22];
14 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
15 int n,m;
16 Node st;
17 char Door[4]={'B','Y','R','G'};
18 char Key[4]={'b','y','r','g'};
19 
20 void bfs(){
21     memset(mark,false,sizeof(mark));
22     queue<Node>Q;
23     Node p,q;
24     st.key=st.step=0;
25     mark[st.x][st.y][st.key]=true;
26     Q.push(st);
27     while(!Q.empty()){
28         p=Q.front();
29         Q.pop();
30         if(map[p.x][p.y]=='X'){
31             printf("Escape possible in %d steps.\n",p.step);
32             return ;
33         }
34         for(int i=0;i<4;i++){
35             q.x=p.x+dir[i][0];
36             q.y=p.y+dir[i][1];
37             q.step=p.step+1;
38             q.key=p.key;
39             if(q.x<1||q.x>n||q.y<1||q.y>m||map[q.x][q.y]=='#')
40                 continue;
41             if(isupper(map[q.x][q.y])&&map[q.x][q.y]!='X'){
42                 for(int j=0;j<4;j++){
43                     if(map[q.x][q.y]==Door[j]){
44                         if(q.key&(1<<j)){
45                             if(!mark[q.x][q.y][q.key]){
46                                 mark[q.x][q.y][q.key]=true;
47                                 Q.push(q);
48                             }
49                             break;
50                         }
51                     }
52                 }
53             }else if(islower(map[q.x][q.y])){
54                 for(int j=0;j<4;j++){
55                     if(map[q.x][q.y]==Key[j]){
56                         if((q.key&(1<<j))==0){
57                             q.key+=(1<<j);
58                         }
59                         if(!mark[q.x][q.y][q.key]){
60                             mark[q.x][q.y][q.key]=true;
61                             Q.push(q);
62                         }
63                     }
64                 }
65             }else {
66                 if(!mark[q.x][q.y][q.key]){
67                     mark[q.x][q.y][q.key]=true;
68                     Q.push(q);
69                 }
70             }
71         }
72     }
73     puts("The poor student is trapped!");
74 }
75 
76 
77 int main(){
78     while(scanf("%d%d",&n,&m),(n+m)){
79         for(int i=1;i<=n;i++){
80             scanf("%s",map[i]+1);
81             for(int j=1;j<=m;j++){
82                 if(map[i][j]=='*')st.x=i,st.y=j;
83             }
84         }
85         bfs();
86     }
87     return 0;
88 }
View Code