hdu 5025 Saving Tang Monk 状态压缩dp+广搜

作者：jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4092939.html

题目链接：hdu 5025 Saving Tang Monk 状态压缩dp+广搜

使用dp[x][y][key][s]来记录孙悟空的坐标(x,y)、当前获取到的钥匙key和打死的蛇s。由于钥匙具有先后顺序，因此在钥匙维度中只需开辟大小为10的长度来保存当前获取的最大编号的钥匙即可。蛇没有先后顺序，其中s的二进制的第i位等于1表示打死了该蛇，否则表示没打死。然后进行广度优先搜索即可，需要注意的是即使目前没有拿到第k-1把钥匙，也可以经过房间k或唐僧，只不过无法获取钥匙k和救唐僧而已。

代码如下：

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <iostream>
  4 #include <cstring>
  5 #include  <queue>
  6 #include  <limits.h>
  7 #define     MAXN 101
  8 #define     MAXM 10
  9 using namespace std;
 10 int dir[4][2]={{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
 11 char map[MAXN][MAXN];
 12 int bin[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096};
 13 int dp[MAXN][MAXN][10][35];
 14 int n, m;
 15 class state
 16 {
 17     public:
 18         int x, y, step, key, s;
 19 };
 20 state start, ed;
 21 void solve()
 22 {
 23     memset(dp, -1, sizeof(dp));
 24     queue<state> qu; 
 25     qu.push(start);
 26     int res = INT_MAX;
 27     while( qu.size() > 0 )
 28     {
 29         state cur = qu.front();
 30         qu.pop();
 31         for( int i = 0 ; i < 4 ; i++ )
 32         {
 33             if( cur.x == ed.x && cur.y == ed.y && cur.key== m )
 34             {
 35                 res = min(res, cur.step);
 36                 continue;
 37             }
 38             state next;
 39             next.x = cur.x+dir[i][0];
 40             next.y = cur.y+dir[i][1];
 41             next.key = cur.key;
 42             next.s = cur.s;
 43             next.step = cur.step;
 44             if( next.x < 0 || next.x >= n || next.y < 0 || next.y >= n )//åºç
 45             {
 46                 continue;
 47             }
 48             char tmp = map[next.x][next.y];
 49             if( tmp  == '#' )//é·é±
 50             {
 51                 continue;
 52             }
 53             if( tmp >= '1' && tmp <= '9' && cur.key >= tmp-'0'-1 )//æé¥å
 54             {
 55                 next.step = cur.step+1;
 56                 next.key = max(cur.key, tmp - '0');
 57                 next.s = cur.s;
 58             }
 59             else if( tmp >= 'A' && tmp <= 'F')//è
 60             {
 61                 if( cur.s/bin[tmp-'A']%2 == 1 )
 62                 {
 63                     next.step = cur.step + 1;    
 64                 }
 65                 else
 66                 {
 67                     next.step = cur.step + 2;
 68                 }
 69                 next.key = cur.key;
 70                 next.s = cur.s | bin[tmp-'A'];
 71             }
 72             else
 73             {
 74                 next.key = cur.key;
 75                 next.step = cur.step+1;
 76                 next.s = cur.s;
 77             }
 78             int dptmp = dp[next.x][next.y][next.key][next.s];
 79             if( dptmp < 0 )
 80             {
 81                 dp[next.x][next.y][next.key][next.s] = next.step;
 82                 qu.push(next);
 83             }
 84             else if(dptmp > next.step)
 85             {
 86                 dp[next.x][next.y][next.key][next.s] = next.step;
 87                 qu.push(next);
 88             }
 89         }
 90     }
 91     if( res == INT_MAX )
 92     {
 93         printf("impossible
");
 94         return;
 95     }
 96     printf("%d
", res);
 97 }
 98 int main(int argc, char *argv[])
 99 {
100     char tmp[MAXN+1];
101     while(1)
102     {
103         scanf("%d%d", &n, &m);
104         if( n == 0 && m == 0 ) return 0;
105         int sn = 0;
106         for( int i = 0 ; i < n ; i++ )
107         {
108             scanf("%s", tmp); 
109             for( int j = 0 ; j < n ; j++ )
110             {
111                 if( tmp[j] == 'K' )
112                 {
113                     start.x = i;
114                     start.y = j;
115                     start.key = 0;
116                     start.step = 0;
117                     start.s = 0;
118                 }
119                 else if( tmp[j] == 'T' )
120                 {
121                     ed.x = i;    
122                     ed.y = j;
123                 }
124                 else if( tmp[j] == 'S' )
125                 {
126                     map[i][j] = 'A'+sn;
127                     sn++;
128                     continue;
129                 }
130                 map[i][j] = tmp[j];
131             }
132         }
133         solve();
134     }
135 }

View Code