UVA - 11624:Fire! (BFS)

 https://vjudge.net/problem/UVA-11624

题意分析：

一个人要逃离迷宫，迷宫的一些地方有火，每1分钟火会蔓延周围4块地板，人可以向4块地板移动，求人能逃出的最短时间，如果不能逃出，输出IMPOSSIBLE。

解题思路：

先一遍bfs遍历地板着火需要多少分钟，再一遍bfs遍历人能走的地方，如果，到达该地点的最短时间大于等于着火时间，那么这个地方就不能去，最后判断一下是不是来到了迷宫外面。

#include 
#include 
#include 
#include 
using namespace std;
#define N 1020
char map[N][N];
int book[N][N], F[N][N];struct edge {int x;int y;int temp;
}e;
int nexts[4][2] = { 1,0, -1,0, 0,1, 0,-1 };
queueq;
int main()
{int T, i, j, k, t, R, C, jx, jy, tx, ty, temp;scanf("%d", &T);while (T--){memset(book, 0, sizeof(book));memset(F, 0x3f, sizeof(F));scanf("%d%d", &R, &C);for (i = 0; i < R; i++)scanf("%s", map[i]);temp = 0;for(i = 0; i < R; i++)for(j = 0; j < C; j++){if (map[i][j] == 'J'){jx=i;jy=j;}if(map[i][j]=='F'){q.push({i, j, 0});book[i][j]=1;}}while(!q.empty()){e=q.front();q.pop();F[e.x][e.y]=e.temp;for(i = 0; i < 4; i++){tx = e.x;ty = e.y;tx+=nexts[i][0];ty+=nexts[i][1];if(tx>=0 && ty>=0 && tx= R || ty >= C){temp=1;break;}	}if(temp==1)break;for(i = 0; i < 4; i++){tx=e.x;ty=e.y;tx+=nexts[i][0];ty+=nexts[i][1];if(tx>=0 && ty>=0 && tx

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