2018年萨马拉地区大学生编程竞赛H题的BFS算法如何改写成长尾？

本文共计1030个文字，预计阅读时间需要5分钟。

你玩了一款新的RPG游戏。游戏中的世界地图由一个n×m的网格细胞表示。任何停留在某个细胞的角色都可以向四个方向移动——向左、向右、向前和向后，但不能离开这个网格。

You play a new RPG. The world map in it is represented by a grid of n × m cells. Any playing character staying in some cell can move from this cell in four directions — to the cells to the left, right, forward and back, but not leaving the world map.

Monsters live in some cells. If at some moment of time you are in the cell which is reachable by some monster in d steps or less, he immediately runs to you and kills you.

You have to get alive from one cell of game field to another. Determine whether it is possible and if yes, find the minimal number of steps required to do it.

Input
The first line contains three non-negative integers n, m and d (2 ≤ n·m ≤ 200000, 0 ≤ d ≤ 200000) — the size of the map and the maximal distance at which monsters are dangerous.

Each of the next n lines contains m characters. These characters can be equal to «.», «M», «S» and «F», which denote empty cell, cell with monster, start cell and finish cell, correspondingly. Start and finish cells are empty and are presented in the input exactly once.

Output
If it is possible to get alive from start cell to finish cell, output minimal number of steps required to do it. Otherwise, output «-1».

Examples
Input
5 7 1
S.M…M
…….
…….
M…M..
……F
Output
12
Input
7 6 2
S…..
…M..
……
…..M
……
M…..
…..F
Output
11
Input
7 6 2
S…..
…M..
……
……
…..M
M…..
…..F
Output
-1
Input
4 4 2
M…
.S..
….
…F
Output
-1
Note
Please note that monsters can run and kill you on start cell and on finish cell as well.

很有意思的bfs ，
这里的怪物在d 步以内会攻击你，所以我们可以先bfs 将怪物所能打击的范围标记，
如果我们对于从S开始的bfs 发现这个位置距离怪物<=d ，那么就不能走；

#include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<vector> #include<queue> #include<string> #include<bitset> #include<ctime> #include<deque> typedef long long ll; using namespace std; typedef unsigned long long int ull; #define maxn 300005 #define ms(x) memset(x,0,sizeof(x)) #define Inf 0x7fffffff #define inf 0x3f3f3f3f const long long int mod = 1e9 + 7; #define pi acos(-1.0) #define pii pair<int,int> #define eps 1e-7 #define pll pair<ll,ll> ll quickpow(ll a, ll b) { ll ans = 1; a = a % mod; while (b > 0) { if (b % 2)ans = ans * a; b = b / 2; a = a * a; } return ans; } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } vector<char>s[maxn]; vector<int>dis1[maxn], dis2[maxn]; char ch[maxn]; int n, m, d, sx, sy, fx, fy; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; queue<pii>q; int bfs(int x, int y) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dis2[i][j] = inf; } } dis2[x][y] = 0; if (dis1[x][y] > d)q.push(pii(x, y)); while (!q.empty()) { pii now = q.front(); q.pop(); int x = now.first, y = now.second; if (x == fx && y == fy)break; for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (xx<1 || xx>n || yy<1 || yy>m || dis1[xx][yy] <= d || dis2[xx][yy] != inf) continue; dis2[xx][yy] = dis2[x][y] + 1; q.push(pii(xx, yy)); } } return dis2[fx][fy]; } int main() { //ios::sync_with_stdio(false); cin >> n >> m >> d; for (int i = 1; i <= n; i++) { dis1[i].resize(m + 1); dis2[i].resize(m + 1); s[i].resize(m + 1); } for (int i = 1; i <= n; i++) { scanf("%s", ch + 1); s[i].push_back(0); for (int j = 1; j <= m; j++) { s[i][j] = ch[j]; if (s[i][j] == 'S')sx = i, sy = j; if (s[i][j] == 'F')fx = i, fy = j; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dis1[i][j] = inf; if (s[i][j] == 'M')dis1[i][j] = 0, q.push(pii(i, j)); } } while (!q.empty()) { pii now = q.front(); q.pop(); int x = now.first, y = now.second; for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (xx<1 || xx>n || yy<1 || yy>m || dis1[xx][yy] != inf) continue; dis1[xx][yy] = dis1[x][y] + 1; q.push(pii(xx, yy)); } } int ans = bfs(sx, sy); if (ans == inf)cout << -1 << endl; else cout << ans << endl; }