首页 > 代码库 > HDU 5025Saving Tang Monk BFS + 二进制枚举状态
HDU 5025Saving Tang Monk BFS + 二进制枚举状态
3A的题目，第一次TLE，是因为一次BFS起点到终点状态太多爆掉了时间。
第二次WA，是因为没有枚举蛇的状态。
解体思路：
因为蛇的数目是小于5只的，那就首先枚举是否杀死每只蛇即可。
然后多次BFS，先从起点到第一把钥匙，不能往回走，要用VIS数组标记。
第二次从第一把钥匙走到第二把钥匙。
最后一次从最后一把钥匙走到终点即可。
Tips 1: 在每次BFS过程中使用优先队列保证每次是最小步长的状态。
Tips2 :使用二进制枚举蛇的状态
Tips3:首先使用DFS判断是否绝对有解，如果无解输出"impossible"，如果有解则继续。
Tips4:多次 BFS,而不是一次BFS，否则会导致状态太多TLE
代码如下：
1 //#pragma comment(linker, "/STACK:16777216") //for c++ Compiler 2 #include <stdio.h> 3 #include <iostream> 4 #include <cstring> 5 #include <cmath> 6 #include <stack> 7 #include <queue> 8 #include <vector> 9 #include <algorithm> 10 #define ll long long 11 #define Max(a,b) (((a) > (b)) ? (a) : (b)) 12 #define Min(a,b) (((a) < (b)) ? (a) : (b)) 13 #define Abs(x) (((x) > 0) ? (x) : (-(x))) 14 using namespace std; 15 16 const int INF = 0x3f3f3f3f; 17 const int MAXN = 220; 18 const double eps = 1e-9; 19 20 struct node{ 21 int x,y,step; 22 }; 23 24 char map[105][105]; 25 int vis[105][105]; 26 int to[4][2]= {1,0,-1,0,0,1,0,-1}; 27 int n,m,sx,sy,ex,ey,ans; 28 29 bool operator < (node a, node b){ 30 return a.step > b.step; 31 } 32 33 int check(int x,int y){ 34 if(x<0 || x>=n || y<0 || y>=n) 35 return 1; 36 if(map[x][y]==‘#‘ || vis[x][y]) 37 return 1; 38 return 0; 39 } 40 41 void bfs(int sx, int sy, int k){ 42 int i; 43 priority_queue <node> Q; 44 node a,next; 45 a.x = sx; 46 a.y = sy; 47 a.step = 0; 48 vis[a.x][a.y]=1; 49 Q.push(a); 50 while(!Q.empty()){ 51 a = Q.top(); 52 //printf("x = %d y = %d step = %d\n",a.x,a.y,a.step); 53 Q.pop(); 54 if(k <= m){ 55 if(map[a.x][a.y] == k + ‘0‘){ 56 ans += a.step; 57 ex = a.x; 58 ey = a.y; 59 //printf("%d %d cur _ ans = %d\n",ex, ey,ans); 60 return; 61 } 62 } else{ 63 if(map[a.x][a.y] == ‘T‘){ 64 ans += a.step; 65 ex = a.x; 66 ey = a.y; 67 //printf("%d %d cur _ ans = %d\n",ex, ey,ans); 68 return; 69 } 70 } 71 for(i = 0; i<4; i++){ 72 next = a; 73 next.x+=to[i][0]; 74 next.y+=to[i][1]; 75 if(check(next.x,next.y)) continue; 76 next.step=a.step+1; 77 if(map[a.x][a.y] == ‘S‘){ 78 ++next.step; 79 } 80 vis[next.x][next.y] = 1; 81 Q.push(next); 82 } 83 if(map[a.x][a.y] == ‘S‘){ 84 map[a.x][a.y] = ‘.‘; 85 } 86 } 87 ans =INF; 88 return ; 89 } 90 91 void dfs(int x, int y){ 92 for(int i = 0; i<4; i++){ 93 int _x = x + to[i][0]; 94 int _y = y + to[i][1]; 95 if(check(_x,_y)) continue; 96 if(map[_x][_y] != ‘#‘){ 97 vis[_x][_y] = 1; 98 dfs(_x,_y); 99 }100 }101 }102 int main(){103 int i,j,cc,s_flag;104 while(EOF != scanf("%d%d",&n,&m)){105 if(n == 0 && m == 0) break;106 s_flag = 0;107 node S[6];108 for(i = 0; i<n; i++)109 scanf("%s",map[i]);110 for(i = 0; i<n; i++){111 for(j = 0; j<n; j++){112 if(map[i][j]==‘K‘){113 sx = i;114 sy = j;115 }else if(map[i][j] == ‘T‘){116 ex = i,ey = j;117 }else if(map[i][j] == ‘S‘){118 S[s_flag].x = i, S[s_flag++].y = j;119 }120 }121 }122 memset(vis,0,sizeof(vis));123 vis[sx][sy] = 1;124 dfs(sx,sy);125 int kkk[11];126 bool flag = false;127 memset(kkk, 0, sizeof(kkk));128 for(i = 0; i < n; ++i){129 for(j = 0; j < n; ++j){130 if(map[i][j] >= ‘1‘ && map[i][j] <= ‘9‘ && vis[i][j]){131 kkk[map[i][j] - ‘0‘] = 1;132 }133 }134 }135 for(i = 1; i <= m; ++i){136 if(!kkk[i]) break;137 }138 if(i == m + 1) flag = true;139 140 if(vis[ex][ey] == 0 || !flag){141 printf("impossible\n");142 continue;143 }144 s_flag = 0;145 for(i = 0; i<n; i++){146 for(j = 0; j<n; j++){147 if(map[i][j] == ‘S‘){148 S[s_flag].x = i, S[s_flag++].y = j;149 }150 }151 }152 int minans=INF;153 for(cc = 0; cc < (1 << s_flag); ++cc){154 ans = 0;155 for(i = 0; i <s_flag; ++i){156 if((1 << i) & cc){157 map[S[i].x][S[i].y] = ‘.‘;158 ans++;159 }160 else {161 map[S[i].x][S[i].y] = ‘#‘;162 }163 }164 for(i = 0; i < n; ++i){165 for(j = 0; j < n; ++j){166 if(map[i][j] == ‘K‘){167 ex = i;168 ey = j;169 }170 }171 }172 for(int k = 1; k <= m + 1; ++k){173 memset(vis, 0, sizeof(vis));174 sx = ex;175 sy = ey;176 bfs(sx, sy, k);177 }178 minans=min(minans,ans);179 }180 printf("%d\n",minans);181 }182 return 0;183 }
HDU 5025Saving Tang Monk BFS + 二进制枚举状态
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。