本文主要是介绍UVA 11624--Fire!，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：这是题目
题意：John在迷宫工作，迷宫着火了，火从四个方向扩散，问John是否能够逃出来。
思路：宽搜，两个宽搜，一个是火，一个是John。有以下几点要注意：
1. 火的位置可能有多个，之前wa在这。从“Unfortunately, portions of the maze havecaught on fire”可以得知。
2. John就在出口（边界），后来wa在这没有考虑到。
3. 我是火和John同时搜的，但是先判断火会不会烧到，然后再判断人要不要走，所以后来错在取人能走的路的队首判断是否是边界，但是由于我是先判断火的，火会把John在的出口烧了，所以会判断为走不出来，即样例
3 3
#JF
###
###
本来应该是1，结果我是IMPOSSIBLE。
所以在外面就判断一下起点是否是终点。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;const int MAX = 1005;
const int INF = 0x3f3f3f3f;
char _map[MAX][MAX];
bool visit[MAX][MAX];
int d[MAX][MAX];
int x[4] = {-1, 0, 1, 0};
int y[4] = {0, 1, 0, -1};int co;
int r, c;
int sx, sy;
int num;
struct node {int xi, yi;int step;
}ff[MAX * MAX], jj[MAX * MAX], f[MAX * MAX];bool OK(node en) {if ((en.xi == 0 || en.xi == r - 1 || en.yi == 0 || en.yi == c - 1) && !visit[en.xi][en.yi]) {return true;}return false;
}bool bfs() {queue <node> q;node start;start.xi = sx;start.yi = sy;start.step = 1;d[sx][sy] = 1;q.push(start);queue <node> fire;for (int i = 0; i < co; i++) {fire.push(f[i]);}while (!q.empty()) {int k1 = 0;while (!fire.empty()) {node fhead, ftail;fhead = fire.front();fire.pop();for (int i = 0; i < 4; i++) {int xx = fhead.xi + x[i];int yy = fhead.yi + y[i];if (xx >= 0 && xx < r && yy >= 0 && yy < c && !visit[xx][yy]) {ftail.xi = xx;ftail.yi = yy;visit[xx][yy] = true;ff[k1++] = ftail;}}}for (int i = 0; i < k1; i++)fire.push(ff[i]);//前1s火能够到的点int k2 = 0;while(!q.empty()) {node head, tail;head = q.front();q.pop();
// if (OK(head)) {
// num = head.step;
// return true;
// }//之前wa在这，在队首判断，会出错for (int i = 0; i < 4; i++) {int xx = head.xi + x[i];int yy = head.yi + y[i];if (xx >= 0 && xx < r && yy >= 0 && yy < c && !visit[xx][yy]&& d[xx][yy] > head.step + 1) {tail.xi = xx;tail.yi = yy;tail.step = head.step + 1;d[xx][yy] = tail.step;jj[k2++] = tail;if (OK(tail)) {num = tail.step;return true;}//每入一个点判断是否是出口}}}for (int i = 0; i < k2; i++)q.push(jj[i]);//前1s John能走到的点}return false;
}int main() {int t;scanf("%d", &t);while(t--) {scanf("%d%d", &r, &c);co = 0;memset(visit, false, sizeof(visit));for (int i = 0; i < r; i++)scanf("%s", _map[i]);for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {d[i][j] = INF;if (_map[i][j] == 'J') {sx = i;sy = j;}else if (_map[i][j] == '#') {visit[i][j] = true;}else if (_map[i][j] == 'F') {//可能多处火f[co].xi = i;f[co].yi = j;co++;visit[i][j] = true;}}}node start;start.xi = sx;start.yi = sy;if (OK(start)) {printf("1\n");}//判断起点是否是出口else if (bfs()) {printf("%d\n", num);}else {printf("IMPOSSIBLE\n");}}return 0;
}
这篇关于UVA 11624--Fire!的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
