UVA11624--Fire!（BFS）

题意： 一个人被困在迷宫里，迷宫有若干着火点（注意是若干，有可能不只一个着火点），人每分钟可以跑上下左右一个方向的一个单位距离，火每次会往上下左右四个方向全部烧一个单位距离，求人逃出迷宫的最小时间（出迷宫矩阵外就算逃出），要是不行就输出"IMPOSSIBLE".

思路： 很明显是BFS，要是没有火就是一个经典的bfs迷宫问题了。加上着火点的存在后，BFS的方式就变了一下。
刚开始还是想一次BFS，把每次人和火都入队，但是这样存在对于同一时间同一位置人比火先进队时(因为根据相对位置的不同每个相同时间点人和火入队顺序无法确定)，火便无效了，而对于这种相同时间，人是不可以走的。
故做一点变式：把vis数组改成火或墙最早能到达的时间，先BFS一次更新除墙外每个位置着火点的能到达的最早时间；接下来对人进行BFS，某一点能走的条件是人走到该点的时间小于火烧到该点的时间。

代码如下：

#include
#include
#include
#include
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1050;
char mp[maxn][maxn];
int time_map[maxn][maxn];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m;
struct node
{int x,y;int ti;
}; 
queue<node>f;
queue<node>q;bool check(int x,int y)
{if(x>=1&&x<=n&&y>=1&&y<=m) return true;else return false;
}void bfs1()//先bfs出time_map; 
{while(!f.empty()){node now=f.front();f.pop();for(int i=0;i<4;i++){int dx=now.x+dir[i][0];int dy=now.y+dir[i][1];if(check(dx,dy)&&now.ti+1<time_map[dx][dy]){node in;in.x=dx;in.y=dy;in.ti=now.ti+1;f.push(in);time_map[dx][dy]=in.ti;}}}
}void bfs2()
{while(!q.empty()){node now=q.front();q.pop();if(!check(now.x,now.y)){printf("%d\n",now.ti);return;}for(int i=0;i<4;i++){int dx=now.x+dir[i][0];int dy=now.y+dir[i][1];if(now.ti+1<time_map[dx][dy]){time_map[dx][dy]=now.ti+1;node in;in.ti=now.ti+1;in.x=dx;in.y=dy;q.push(in);}}}printf("IMPOSSIBLE\n");
}int main()
{int i,j;int t;scanf("%d",&t);while(t--){memset(time_map,INF,sizeof(time_map));while(!q.empty()) q.pop();while(!f.empty()) f.pop();scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%s",mp[i]+1);}for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(mp[i][j]=='#') time_map[i][j]=0;if(mp[i][j]=='J'){node in;in.x=i;in.y=j;in.ti=0;q.push(in);time_map[i][j]=0;}if(mp[i][j]=='F'){node in;in.ti=0;in.x=i;in.y=j;f.push(in);time_map[i][j]=0;}}}bfs1();bfs2();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！