题意
有一个人 有一些火
人 在每一秒 可以向 上下左右的空地走 火每秒 也会向 上下左右的空地 蔓延
求 人能不能跑出来 如果能 求最小时间
思路
有一个 坑点 火是 可能有 多处 的 样例中 只有一处
然后 先让 火 蔓延 再让人走
BFS
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1); const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 1e3 + 5; const int MOD = 1e9 + 7; string G[maxn]; int Move[8][2] { -1, 0, 1, 0, 0,-1, 0, 1, -1, 1, -1,-1, 1, 1, 1,-1, }; int n, m; int ans; bool ok(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m || G[x][y] != '.' ) return false; return true; } bool edge(int x, int y) { if (x == 0 || x == n - 1 || y == 0 || y == m - 1) return true; return false; } struct Node { int x, y, step; }tmp; queue <Node> fire, q; void bfs() { int len = fire.size(); for (int i = 0; i < len; i++) { int x = fire.front().x; int y = fire.front().y; fire.pop(); for (int j = 0; j < 4; j++) { tmp.x = x + Move[j][0]; tmp.y = y + Move[j][1]; if (ok(tmp.x, tmp.y)) { G[tmp.x][tmp.y] = 'F'; fire.push(tmp); } } } len = q.size(); for (int i = 0; i < len; i++) { int x = q.front().x; int y = q.front().y; int step = q.front().step; q.pop(); if (edge(x, y)) { ans = step; return; } for (int j = 0; j < 4; j++) { tmp.x = x + Move[j][0]; tmp.y = y + Move[j][1]; if (ok(tmp.x, tmp.y)) { tmp.step = step + 1; G[tmp.x][tmp.y] = '*'; q.push(tmp); } } } if (q.size()) bfs(); } int main() { int t; cin >> t; while (t--) { while (!fire.empty()) fire.pop(); while (!q.empty()) q.pop(); scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { cin >> G[i]; for (int j = 0; j < m; j++) { if (G[i][j] == 'J') { tmp.x = i; tmp.y = j; tmp.step = 0; q.push(tmp); G[i][j] = '.'; } else if (G[i][j] == 'F') { tmp.x = i; tmp.y = j; fire.push(tmp); } } } ans = -1; bfs(); if (ans == -1) printf("IMPOSSIBLE\n"); else printf("%d\n", ans + 1); } }转载于:https://www.cnblogs.com/Dup4/p/9433134.html
