首页 > 代码库 > UVa11624 BFS
UVa11624 BFS
题意：有一个迷宫，迷宫中有许多火堆，Joe每次只走一步，火也是一次向四个方向蔓延一步，Joe不可以遇到火和障碍物，问Joe能否走出迷宫（只要到达边界居、就可以了）。
思路：先计算每个点最先什么时候起火，再判断Joe到达这个点时是否已经起火了，这样就可以。
代码：
// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2671#include<cstdio>#include<algorithm>#include<queue>#include<cstring>const int maxn = 1009;const int inf = 1<<30;struct node{ int x,y; node(int a = 0,int b = 0) : x(a),y(b){}};std::queue<node> que;char map[maxn][maxn];int fire[maxn][maxn],vis[maxn][maxn],dis[maxn][maxn];int dxy[4][2] ={0,1,-1,0,1,0,0,-1};int n, m;void BFSF(){ node p; while(!que.empty()) { p = que.front(); que.pop(); for(int i=0;i<4;i++) { int dx = p.x + dxy[i][0]; int dy = p.y + dxy[i][1]; if(dx >= 0 && dx < n && dy >= 0 && dy < m && !vis[dx][dy] && map[dx][dy] == ‘.‘) { fire[dx][dy] = fire[p.x][p.y] +1; vis[dx][dy] = 1; que.push(node(dx,dy)); } } }}void BFS(int sx,int sy){ que.push(node(sx,sy)); node p; dis[sx][sy] = 0; vis[sx][sy] = 1; while(!que.empty()) { p = que.front(); que.pop(); for(int i=0;i<4;i++) { int dx = p.x + dxy[i][0]; int dy = p.y + dxy[i][1]; if(dx >= 0 && dx < n && dy >= 0 && dy < m && !vis[dx][dy] && map[dx][dy] == ‘.‘ && dis[p.x][p.y]+1 < fire[dx][dy]) { dis[dx][dy] = dis[p.x][p.y] +1; vis[dx][dy] = 1; que.push(node(dx,dy)); } } }}void init(){ while(!que.empty()) que.pop(); memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) fire[i][j] = dis[i][j] = inf; }inline int min(int a,int b){ if(a < b)return a; return b;}int main(){ int t,i,j; scanf("%d",&t); while(t--) { int jx,jy; scanf("%d%d",&n,&m); init(); for(i=0;i<n;i++) { scanf("%s",map[i]); for(j=0;j<m;j++) { if(map[i][j] == ‘F‘) { que.push(node(i,j)); vis[i][j] = 1; fire[i][j] = 0; } if(map[i][j] == ‘J‘) jx = i,jy = j; } } BFSF(); memset(vis,0,sizeof(vis)); BFS(jx,jy); int ans = inf; for(i=0;i<m;i++) { ans = min(ans,dis[0][i]); ans = min(ans,dis[n-1][i]); } for(i=0;i<n;i++) { ans = min(ans,dis[i][0]); ans = min(ans,dis[i][m-1]); } if(ans == inf) printf("IMPOSSIBLE\n"); else printf("%d\n",ans+1); } return 0;}/*24 4#####JF##..##..#3 3####J.#.F */
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。