本文主要是介绍FZU2150-Fire Game （双点BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://vjudge.net/problem/FZU-2150
题意：最多可以选择两处火源，要把整个地图上的草地都点燃，火可以往上下左右四个方向扩散，能否把所有的草地都点燃，能的话输出最少时间，不能输出-1；'#'代表草地，'.'表示空地，空地不会起火。
思路：因为地图很小，所以暴力枚举两个起火点然后两个点同时进行BFS。因为不知道终点所以我们需要把走到每一个点的时间都存下来，然后遍历一下，那么草地那些点中起火时间最晚的那个点，也就是当前枚举这两个起火点的点燃所有草地的时间。对于这些维护一个最小值作为答案。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 15;
int n, m, ans;
int STEP[MAXN][MAXN], dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char MAP[MAXN][MAXN];
struct Point
{int x, y, step;
}NOW,NEXT;
bool vis[MAXN][MAXN];
int get_ans()
{int MAX = 0;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (MAP[i][j] == '#'){MAX = max(MAX, STEP[i][j]);}}}ans = min(ans,MAX);
}
void bfs(int x1, int y1, int x2, int y2)
{memset(STEP, INF, sizeof(STEP));memset(vis, 0, sizeof(vis));queue<Point> q;NOW.x = x1; NOW.y = y1; NOW.step = 0;q.push(NOW);NOW.x = x2; NOW.y = y2; NOW.step = 0;q.push(NOW);while (!q.empty()){NOW = q.front();q.pop();STEP[NOW.x][NOW.y] = min(NOW.step, STEP[NOW.x][NOW.y]);for(int i = 0; i < 4; i++){int X = NOW.x + dir[i][0], Y = NOW.y + dir[i][1];if(X >= 0 && Y >= 0 && X < n && Y < m && MAP[X][Y] == '#' && !vis[X][Y]){vis[X][Y] = true;NEXT.x = X; NEXT.y = Y; NEXT.step = NOW.step + 1;q.push(NEXT);}}}
}
int main()
{int T, CASE = 1;scanf("%d", &T);while (T--){ans = INF;scanf("%d%d", &n, &m);for (int i = 0; i < n; i++) scanf("%s",MAP[i]);for (int x1 = 0; x1 < n; x1++){for (int y1 = 0; y1 < m; y1++){for (int x2 = 0; x2 < n; x2++){for (int y2 = 0; y2 < m; y2++){if (MAP[x1][y1] == '#' && MAP[x2][y2] == '#'){bfs(x1, y1, x2, y2);get_ans();}}}}}if (ans == INF) ans = -1;printf("Case %d: %d\n",CASE++,ans);}return 0;
}
这篇关于FZU2150-Fire Game （双点BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
