2014 网选 广州赛区 hdu 5025 Saving Tang Monk(bfs+四维数组记录状态)

简介:
 1 /*
  2     这是我做过的一道新类型的搜索题!从来没想过用四维数组记录状态!
  3     以前做过的都是用二维的!自己的四维还是太狭隘了.....
  4     
  5     题意:悟空救师傅 ! 在救师父之前要先把所有的钥匙找到!
  6     每种钥匙有 k 种, 每一种有多个! 只要求找到每一种的其中一个就可以!
  7     找钥匙的顺序按照 第1种, 第2种, 第3种 ....第k种! 
  8     找钥匙的时间是一步, 走到相邻空地的时间是一步, 打蛇的时间就是两步!
  9     求找到师傅的最少步数! 
 10     
 11     这里说一下 state[N][N][10][35]表示的含义: ->state[x][y][i][j] 
 12     前两维就不用说了,就是地图上的坐标, 第三维表示的是当前找到第几把钥匙
 13     第四维表示的沿着一条路径走到 (x, y)找到 第 i 把钥匙打掉了哪几条蛇!
 14     将 j 拆分成 二进制, 从右往左数, 如果第 k 为是1, 表示第 k 条 蛇杀掉了! 
 15 */ 
 16 
 17 #include<iostream>
 18 #include<cstdio>
 19 #include<cstring>
 20 #include<algorithm>
 21 #include<queue>
 22 
 23 #define N 105
 24 using namespace std;
 25 
 26 char mp[105][105];
 27 
 28 bool state[N][N][10][35];
 29 
 30 int bx, by;
 31 
 32 struct node{
 33     int x, y;
 34     int numk, snk;
 35     int step;
 36     node(){}
 37     
 38     node(int x, int y, int numk, int snk, int step){
 39         this->x = x;
 40         this->y = y;
 41         this->numk = numk;
 42         this->snk = snk;
 43         this->step = step;
 44     }
 45 };
 46 
 47 int n, m;
 48 int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
 49 bool operator < (node a, node b) {
 50     return a.step > b.step;
 51 }
 52 
 53 priority_queue<node>q;
 54 
 55 bool bfs(){
 56     while(!q.empty()) q.pop();
 57     memset(state, false, sizeof(state));
 58     q.push( node(bx, by, 0, 0, 0) );
 59     state[bx][by][0][0] = true;
 60     while( !q.empty() ) {
 61         node cur = q.top();
 62         q.pop();
 63         for(int i=0; i<4; ++i){
 64             int x = cur.x + dir[i][0];
 65             int y = cur.y + dir[i][1];
 66             if(x<1 || x>n || y<1 || y>n || mp[x][y]=='#') continue;
 67             int numk = cur.numk, snk = cur.snk, step = cur.step;
 68             if(mp[x][y] == '.')
 69                 step += 1;
 70             else if( mp[x][y] >= '1' && mp[x][y] <= '9'){
 71                 if( numk + 1 == mp[x][y] - '0' )
 72                     numk += 1;
 73                 step += 1;
 74             }
 75             else if( mp[x][y] >= 'A' && mp[x][y] <= 'E' ){//这一步是关键 
 76                 int cnt = mp[x][y] - 'A' + 1; 
 77                 if(    (1 << (cnt-1) ) & snk ) step += 1;//如果这一条蛇已经被打过了,也就是一条路又折回到这一个点 
 78                 else{//在这一条路上,这条蛇没有被打过,那就将它打掉,并标记这条蛇打过了! 
 79                     step += 2;
 80                     snk ^= ( 1 << (cnt-1) );
 81                 }
 82             }
 83             else if( mp[x][y] == 'T' && numk == m ){
 84                 printf("%d\n", step + 1);
 85                 return true;
 86             }
 87             else step += 1;
 88             
 89             if( state[x][y][numk][snk] )  continue;
 90             state[x][y][numk][snk] = true;
 91             q.push( node(x, y, numk, snk, step) );
 92         }
 93     }
 94     return false;
 95 }
 96 
 97 int main(){
 98     while( scanf("%d%d", &n, &m) && (n ||m) ) {
 99         int cntS = 0;
100         for(int i = 1; i <= n; ++ i){
101             scanf("%s", mp[i] + 1);
102             for(int j = 1; j <=n; ++ j)
103                 if(mp[i][j] == 'K'){
104                     bx = i;
105                     by = j;
106                 }
107                 else if(mp[i][j] == 'S')
108                     mp[i][j] = 'A' + cntS++;
109         }
110         if( !bfs() )  printf("impossible\n");
111     }
112     return 0;
113 }









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3984954.html,如需转载请自行联系原作者
目录
相关文章
PTA--天梯赛题集题解--打印沙漏
PTA--天梯赛题集题解--打印沙漏
|
9月前
|
算法
【算法挨揍日记】day12——153. 寻找旋转排序数组中的最小值、LCR 173. 点名
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
104 1
|
算法
山东第一届省赛 Greatest Number(优雅暴力+二分)
山东第一届省赛 Greatest Number(优雅暴力+二分)
50 1
2021山东省赛 M . Matrix Problem(构造)
2021山东省赛 M . Matrix Problem(构造)
44 0
|
测试技术
(dfs)(枚举)第十四届蓝桥杯第三次模拟赛:9.最大滑雪长度
(dfs)(枚举)第十四届蓝桥杯第三次模拟赛:9.最大滑雪长度
113 0
|
存储
UPC组队第三场——K: A Famous Grid (BFS+细节)
UPC组队第三场——K: A Famous Grid (BFS+细节)
68 0
UPC组队第三场——K: A Famous Grid (BFS+细节)
【CCCC】L3-018 森森美图 (30分),计算几何+判断三点共线+bfs最短路
【CCCC】L3-018 森森美图 (30分),计算几何+判断三点共线+bfs最短路
124 0
|
人工智能 Python
2019CCPC厦门站 A. Zayin and Bus(bfs 贪心 排序)
2019CCPC厦门站 A. Zayin and Bus(bfs 贪心 排序)
71 0
|
消息中间件 uml
gym102394 2019CCPC哈尔滨 A. Artful Paintings(二分 差分约束 优化)
gym102394 2019CCPC哈尔滨 A. Artful Paintings(二分 差分约束 优化)
151 0
|
机器学习/深度学习
2019CCPC厦门站 H. Zayin and Obstacles(三维前缀和 bfs)
2019CCPC厦门站 H. Zayin and Obstacles(三维前缀和 bfs)
70 0