首页 > 代码库 > 【BFS】uva11624Fire!
【BFS】uva11624Fire!
/* bfs宽度遍历 -------------------------------------------------------------------------- 对人和火同时进行bfs,,注意应该先火后人,即如果在人到达该格子前,格子已经着火 则不应该走,最后人走到边界无路可走,则IMPOSSIBLE!!!!!!!!!!!! --------------------------------------------------------------------------- 两次bfs: bfs1();火 bfs()人: 先bfs1后bfs();;;;;;;;;;;;;;;;;;;;;;;;;;;;或者计算格子着火的时间 -------------------------------------------------------------------------- for(int i=0; i<r; i++)因为火格不止一个,应该for循环 { for(int j=0; j<c; j++) { if(g[i][j] == 'F')火进入队列 { q[rear].x = j; q[rear].y = i; q[rear].step = 0;step置零 q[rear++].flag = 1;标记为火格子 } } } ----------------------------------------------------------------------------- q[rear].x = fx;人(的起点)进入队列 q[rear].y = fy; q[rear].step = 0; q[rear++].flag = 0; ------------------------------------------------------------------------------- if(q[front].flag)火点进行扩展 { for(int i=0; i<4; i++)每次扩展都有4个方向 { xx = q[front].x + step_x[i];更新扩展点的位置 yy = q[front].y + step_y[i]; if(xx < 0 || xx >= c || yy < 0 || yy >= r || g[yy][xx] == '#' || g[yy][xx] == 'F')如果越界,遇到火,障碍物continue continue; g[yy][xx] = 'F';火蔓延至此 q[rear].x = xx;扩展点变为当前点 q[rear].y = yy; q[rear].flag = 1;标记为火 q[rear++].step = q[front].step+1;每次时间加1 } } --------------------------------------------------------------------------------------- for(int i=0; i<4; i++)人扩展 { xx = q[front].x + step_x[i]; yy = q[front].y + step_y[i]; if(vis[yy][xx] || g[yy][xx] == 'F' || g[yy][xx] == '#') continue; if(xx < 0 || xx >= c || yy < 0 || yy >= r) return q[front].step+1; vis[yy][xx] = 1; q[rear].x = xx; q[rear].y = yy; q[rear].flag = 0; q[rear].step = q[front].step + 1; ++rear; ------------------------------------------------------------------------------------ */ #include <iostream> #include <cstdio> #include <cstring> #define INF 0x3f3f3f3f using namespace std; const int MAXN = 1010; struct node { int x, y; int step; int flag; } q[MAXN*MAXN]; int r, c; int fx, fy; int step_x[4] = {1, -1, 0, 0}; int step_y[4] = {0, 0, 1, -1}; char g[MAXN][MAXN]; int vis[MAXN][MAXN]; int bfs() { int front = 0, rear = 0; memset(vis, 0, sizeof(vis)); for(int i=0; i<r; i++) { for(int j=0; j<c; j++) { if(g[i][j] == 'F') { q[rear].x = j; q[rear].y = i; q[rear].step = 0; q[rear++].flag = 1; } } } q[rear].x = fx; q[rear].y = fy; q[rear].step = 0; q[rear++].flag = 0; while(front < rear) { int xx = q[front].x; int yy = q[front].y; if(q[front].flag) { for(int i=0; i<4; i++) { xx = q[front].x + step_x[i]; yy = q[front].y + step_y[i]; if(xx < 0 || xx >= c || yy < 0 || yy >= r || g[yy][xx] == '#' || g[yy][xx] == 'F') continue; g[yy][xx] = 'F'; q[rear].x = xx; q[rear].y = yy; q[rear].flag = 1; q[rear].step = q[front].step+1; ++rear; } } else { for(int i=0; i<4; i++) { xx = q[front].x + step_x[i]; yy = q[front].y + step_y[i]; if(vis[yy][xx] || g[yy][xx] == 'F' || g[yy][xx] == '#') continue; if(xx < 0 || xx >= c || yy < 0 || yy >= r) return q[front].step+1; vis[yy][xx] = 1; q[rear].x = xx; q[rear].y = yy; q[rear].flag = 0; q[rear++].step = q[front].step + 1; } } front++; } return 0; } int main() { //freopen("input.txt","r",stdin); int T; cin>>T; while(T--) { scanf("%d%d",&r,&c); fx = fy = -1; getchar(); for(int i=0; i<r; i++) { gets(g[i]); if(fx == -1) { for(int j=0; j<c; j++) { if(g[i][j] == 'J') { fx = j; fy = i; break; } } } } int time = bfs(); if(time) printf("%d\n",time); else printf("IMPOSSIBLE\n"); } return 0; }-----------
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。