hdu--1429--状压bfs

做这题来为上年上海的那个状压bfs做铺垫 =_=

这题不难就是多开一维存下钥匙的状态就好了表示在 (x,y)这个坐标点已经收集到了哪些钥匙

多做点状压的题目就会来感觉的.

 1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int n , m , t;
 7 const int size = 25;
 8 char mp[size][size];
 9 bool vis[size][size][1<<11];
10 int dir[4][2] = {1,0,-1,0,0,1,0,-1};
11 struct node
12 {
13     int x , y , key , Time;
14     node(){};
15     node( int u , int v , int z , int w ):x(u),y(v),key(z),Time(w){};
16 };
17 queue<node>q;
18 
19 void init( )
20 {
21     memset( vis , false , sizeof(vis) );
22     while( !q.empty() )
23     {
24         q.pop();
25     }
26 }
27 
28 int bfs( int stx , int sty )
29 {
30     int x , y , key;
31     node now;
32     q.push( node(stx,sty,0,0) );
33     vis[stx][sty][0] = true;
34     while( !q.empty() )
35     {
36         now = q.front();
37         q.pop();
38         if( now.Time>=t )
39         {
40             return -1;
41         }
42         if( mp[now.x][now.y]=='^' )
43         {
44             return now.Time;
45         }
46         for( int i = 0 ; i<4 ; i++ )
47         {
48             x = now.x + dir[i][0];
49             y = now.y + dir[i][1];
50             key = 0;
51             if( x>=0 && x<=n-1 && y>=0 && y<=m-1 && mp[x][y]!='*' && !vis[x][y][now.key] )
52             {
53                 if( mp[x][y]>='a' && mp[x][y]<='j' )
54                 {
55                     key |= ( 1<<(mp[x][y]-'a') );
56                 }
57                 else if( mp[x][y]>='A' && mp[x][y]<='J' )
58                 {
59                     if( !( now.key & ( 1<<( mp[x][y]-'A' ) ) ) )
60                     {
61                         continue;
62                     }
63                 }
64                 q.push( node( x , y , now.key|key , now.Time+1 ) );
65                 vis[x][y][now.key] = true;
66             }
67         }
68     }
69     return -1;
70 }
71 
72 int main()
73 {
74     cin.sync_with_stdio(false);
75     int ans , stx , sty;
76     while( cin >> n >> m >> t )
77     {
78         init();
79         for( int i = 0 ; i<n ; i++ )
80         {
81             for( int j = 0 ; j<m ; j++ )
82             {
83                 cin >> mp[i][j];
84                 if( mp[i][j] == '@' )
85                 {
86                     stx = i;
87                     sty = j;
88                 }
89             }
90         }
91         ans = bfs( stx , sty );
92         cout << ans << endl;
93     }
94     return 0;
95 }

View Code

today:

　　我不找你

　　你不找我

　　就这样.......

　　退出各自生活

　　其实就没出现过

just follow your heart