UVA - 11624 - Fire!(BFS逃生问题)

题目链接

题意：

在迷宫内，J表示人，F表示火，火可能不止一处，但是人只有一个，火会向上下左右蔓延，
蔓延速度和人移动速度一至（每次一格，但是可以同时向四个方向）问是否可以成功逃出迷宫，
不能输出IMPOSSIBLE，能的画话输出最短路径。

题解：

每步先让火走–然后人走其他的路–就可以保证人不会被火烧了
先将火入队列最后将人入队列，走的时候判断下是人还是火，如果是人的话看看是否无路可走
注：也可以跑两次BFS，先跑火，再跑人，看人到当前格时间是否小于火的

AC代码：

#include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; char ma[1010][1010]; int n,m,rx,ry,fx,fy; int xx[4]={0,0,1,-1}; int yy[4]={1,-1,0,0}; struct node{ int x,y,step; bool fafe; }now,qian,ff; int bfs(){ queue <node> que; for (int i=0;i<n;i++) for (int j=0;j<m;j++){ if (ma[i][j]=='F'){ now.x=i;now.y=j;now.step=0; now.fafe=true; que.push(now); ma[i][j]='#'; } } now.x=rx;now.y=ry;now.step=0;now.fafe=false; que.push(now); while (!que.empty()){ now=que.front(); que.pop(); if (now.fafe){ for (int i=0;i<4;i++){ int kx=now.x+xx[i]; int ky=now.y+yy[i]; if (kx<0||ky<0||kx==n||ky==m||ma[kx][ky]=='#') continue; { ma[kx][ky]='#'; qian.x=kx;qian.y=ky; qian.step=now.step+1; qian.fafe=true; que.push(qian); } } } else{ for (int i=0;i<4;i++){ int kx=now.x+xx[i]; int ky=now.y+yy[i]; if (kx<0||ky<0||kx==n||ky==m){ return now.step+1; } if (ma[kx][ky]!='#'){ ma[kx][ky]='#'; qian.x=kx;qian.y=ky; qian.step=now.step+1; qian.fafe=false; que.push(qian); } } } } return 0; } int main(){ int t;scanf("%d",&t); while (t--){ scanf("%d%d",&n,&m); for (int i=0;i<n;i++){ scanf("%s",ma[i]); for (int j=0;j<m;j++){ if (ma[i][j]=='J'){ rx=i;ry=j; ma[i][j]='#'; } } } int ans=bfs(); if (ans) printf("%d\n",ans); else printf("IMPOSSIBLE\n"); } return 0; }