HDU1429+bfs+状态压缩

bfs+状态压缩
思路：用2进制表示每个钥匙是否已经被找到。、
  1 /*
  2 bfs+状态压缩
  3 思路：用2进制表示每个钥匙是否已经被找到。
  4 */
  5 #include<algorithm>  
  6 #include<iostream>  
  7 #include<string.h>  
  8 #include<stdlib.h>  
  9 #include<stdio.h>  
 10 #include<math.h>  
 11 #include<queue>  
 12 #include<stack>  
 13 #include<map>  
 14 #include<set>  
 15 using namespace std;  
 16 typedef long long int64;  
 17 //typedef __int64 int64;  
 18 typedef pair<int64,int64> PII;  
 19 #define MP(a,b) make_pair((a),(b))   
 20 const int inf = 0x3f3f3f3f;  
 21 const double pi=acos(-1.0);  
 22 const int dx[]={1,-1,0,0};  
 23 const int dy[]={0,0,1,-1};  
 24 const double eps = 1e-8;  
 25 const int maxm = (1<<10)+5;  
 26 const int maxn = 22;
 27 
 28 bool vis[ maxn ][ maxn ][ maxm ];
 29 char mat[ maxn ][ maxn ];
 30 struct Point {
 31     int x,y,ti,key;
 32 };
 33 Point s,e;
 34 queue<Point>q;
 35 
 36 int bfs( int n,int m,int sumT ){
 37     memset( vis,false,sizeof( vis ) );
 38     while( !q.empty() )
 39         q.pop();
 40     Point cur;
 41     cur = s;
 42     vis[ cur.x ][ cur.y ][ cur.key ] = true;
 43     q.push( cur );
 44     while( !q.empty() ){
 45         cur = q.front();
 46         q.pop();
 47         if( cur.x==e.x && cur.y==e.y  ){
 48             e.ti = min( e.ti,cur.ti );
 49         }
 50         if( cur.ti>=sumT ) continue;
 51         for( int i=0;i<4;i++ ){
 52             Point nxt ;
 53             nxt.x = cur.x + dx[ i ];
 54             nxt.y = cur.y + dy[ i ];
 55             nxt.ti = cur.ti + 1;
 56             nxt.key = cur.key;
 57             if( nxt.x<0||nxt.x>=n||nxt.y<0||nxt.y>=m ) continue;
 58             if( mat[ nxt.x ][ nxt.y ]=='*' ) continue;
 59             if( mat[ nxt.x ][ nxt.y ]>='a' && mat[ nxt.x ][ nxt.y ]<='z' ){
 60                 nxt.key = cur.key|(1<<(mat[ nxt.x ][ nxt.y ]-'a'));
 61             }//there may be a new key
 62             if( vis[ nxt.x ][ nxt.y ][ nxt.key ]==true )
 63                 continue;
 64             vis[ nxt.x ][ nxt.y ][ nxt.key ] = true;
 65             if( mat[ nxt.x ][ nxt.y ]>='A' && mat[ nxt.x ][ nxt.y ]<='Z' ){
 66                 if( nxt.key&(1<<(mat[ nxt.x ][ nxt.y ]-'A')) ){
 67                     q.push( nxt );
 68                 }
 69             }
 70             else 
 71                 q.push( nxt );
 72         }
 73     }
 74     if( e.ti>=sumT )
 75         return -1;
 76     else
 77         return e.ti;
 78 }
 79             
 80 int main(){
 81     int n,m,sumT;
 82     while( scanf("%d%d%d",&n,&m,&sumT)==3 ){
 83         for( int i=0;i<n;i++ ){
 84             scanf("%s",mat[ i ]);
 85             for( int j=0;j<m;j++ ){
 86                 if( mat[ i ][ j ]=='@' ){
 87                     s.x = i;
 88                     s.y = j;
 89                     s.ti = 0;
 90                     s.key = 0;
 91                     mat[ i ][ j ] = '.';
 92                 }
 93                 if( mat[ i ][ j ]=='^' ){
 94                     e.x = i;
 95                     e.y = j;
 96                     e.ti = sumT+1;
 97                     mat[ i ][ j ] = '.';
 98                 }
 99             }
100         }
101         printf("%d
",bfs( n,m,sumT ));
102     }
103     return 0;
104 }
View Code
keep moving...