第二组样例:
题意 给出一个起始位置，然后要跑到这幢建筑物的外面，上下左右四个方向，只要是空地 就可以走 走一步 花费一秒 然后有若干串火苗，每一秒钟 会向上下左右 四个方向的空地 蔓延 但是 逃跑的优先级在先 比如
这个例子 @会先逃到右边，火苗再蔓延
思路 用BFS 记录能到的下一步的位置，然后记录火苗的本次蔓延位置，用双队列，然后先遍历下一步的位置 再遍历火苗蔓延的位置 最后 设置出口条件就可以了 两个出口 ① 当没有下一步的位置 并且当前步没有一步是在边界 就是no ② 当前步在边界 直接更新答案 输出
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> 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; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int maxn = 1e3 + 5; const int MOD = 1e9 + 7; string Map[maxn]; int n, m; int ans; queue <pii> q, f; int Move[4][2] = { -1, 0, //up 1, 0, //down 0,-1, //left 0, 1, //right }; bool out_range(int x, int y) { if (x == 0 || y == 0 || x == (m - 1) || y == (n - 1)) return true; return false; } bool in_range(int x, int y) { if (x >= 0 && x < m && y >= 0 && y < n) return true; return false; } void fire(int x, int y) { int next_x, next_y; for (int i = 0; i < 4; i++) { next_x = x + Move[i][0]; next_y = y + Move[i][1]; if (in_range(next_x, next_y)) { if (Map[next_x][next_y] == '.' || Map[next_x][next_y] == '$') { Map[next_x][next_y] = '*'; f.push(pii(next_x, next_y)); } } } } void dfs(int cur) { int x, y; int next_x, next_y; int len = q.size(); while (len--) { x = q.front().first; y = q.front().second; q.pop(); if (Map[x][y] == '*') continue; if (out_range(x, y)) { ans = cur; return; } for (int i = 0; i < 4; i++) { next_x = x + Move[i][0]; next_y = y + Move[i][1]; if (in_range(next_x, next_y) && Map[next_x][next_y] == '.') { Map[next_x][next_y] = '$'; q.push(pii(next_x, next_y)); } } } if (q.size() == 0) return; else { int len = f.size(); int x, y; while (len--) { x = f.front().first; y = f.front().second; fire(x, y); f.pop(); } dfs(cur + 1); } } int main() { int t; cin >> t; while (t--) { while (!q.empty()) q.pop(); while (!f.empty()) f.pop(); scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { cin >> Map[i]; for (int j = 0; j < n; j++) { if (Map[i][j] == '@') { Map[i][j] = '$'; q.push(pii(i, j)); } else if (Map[i][j] == '*') f.push(pii(i, j)); } } ans = -1; dfs(1); if (ans == -1) printf("IMPOSSIBLE\n"); else printf("%d\n", ans); } }转载于:https://www.cnblogs.com/Dup4/p/9433237.html
