hdu 1429 bfs+状态压缩

对于这类需要钥匙才能通过的迷宫来说，一般visit数组会开成三维的：bool visit[N][N][1 << 10];最后一维表示通过该位置时的拥有的钥匙的情况。
  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cctype>
  5 #include <queue>
  6 using namespace std;
  7 
  8 const int N = 21;
  9 char maze[N][N];
 10 bool visit[N][N][1 << 10];
 11 int dx[] = { 0, 0, 1, -1 };
 12 int dy[] = { 1, -1, 0, 0 };
 13 int sx, sy, ex, ey;
 14 int n, m, t;
 15 
 16 bool ok( int x, int y )
 17 {
 18     return x >= 0 && x < n && y >= 0 && y < m;
 19 }
 20 
 21 struct Node 
 22 {
 23     int x, y, step, state;
 24     Node(){}
 25     Node( int _x, int _y, int _step, int _state )
 26     {
 27         x = _x, y = _y, step = _step, state = _state;
 28     }
 29 };
 30 
 31 queue<Node> q;
 32 
 33 int bfs()
 34 {
 35     while ( !q.empty() ) q.pop();
 36     memset( visit, false, sizeof(visit) );
 37     q.push( Node( sx, sy, 0, 0 ) );
 38     visit[sx][sy][0] = true;
 39     while ( !q.empty() )
 40     {
 41         Node cur = q.front();
 42         q.pop();
 43         if ( cur.step == t ) return -1;
 44         if ( cur.x == ex && cur.y == ey ) return cur.step;
 45         for ( int i = 0; i < 4; i++ )
 46         {
 47             int xx = cur.x + dx[i];
 48             int yy = cur.y + dy[i];
 49             if ( ok( xx, yy ) )
 50             {
 51                 if ( maze[xx][yy] == '*' ) continue;
 52                 if ( isupper( maze[xx][yy] ) )
 53                 {
 54                     int tmp = ( 1 << ( maze[xx][yy] - 'A' ) );
 55                     if ( ( cur.state & tmp ) && !visit[xx][yy][cur.state] )
 56                     {
 57                         q.push( Node( xx, yy, cur.step + 1, cur.state) );
 58                         visit[xx][yy][cur.state] = true;
 59                     }
 60                 }
 61                 else if ( islower( maze[xx][yy] ) )
 62                 {
 63                     int tmp = ( 1 << ( maze[xx][yy] - 'a' ) );
 64                     if ( !visit[xx][yy][cur.state | tmp] )
 65                     {
 66                         q.push( Node( xx, yy, cur.step + 1, cur.state | tmp ) );
 67                         visit[xx][yy][cur.state | tmp] = true;
 68                     }
 69                 }
 70                 else
 71                 {
 72                     if ( !visit[xx][yy][cur.state] )
 73                     {
 74                         q.push( Node( xx, yy, cur.step + 1, cur.state ) );
 75                         visit[xx][yy][cur.state] = true;
 76                     }
 77                 }
 78             }
 79         }
 80     }
 81     return -1;
 82 }
 83 
 84 int main ()
 85 {
 86     while ( scanf("%d%d%d", &n, &m, &t) != EOF )
 87     {
 88         for ( int i = 0; i < n; i++ )
 89         {
 90             scanf("%s", maze[i]);
 91             for ( int j = 0; j < m; j++ )
 92             {
 93                 if ( maze[i][j] == '@' )
 94                 {
 95                     sx = i;
 96                     sy = j;
 97                     maze[i][j] = '.';
 98                 }
 99                 else if ( maze[i][j] == '^' )
100                 {
101                     ex = i;
102                     ey = j;
103                     maze[i][j] = '.';
104                 }
105             }
106         }
107         int ans = bfs();
108         printf("%d
", ans);
109     }
110     return 0;    
111 }