AtCoder AT_abc405_d ABC405D - Escape Route

前言

BFS 算法在 AtCoder 比赛中还是会考的，因为不常练习导致没想到，不仅错误 TLE 了很多，还影响了心态，3 发罚时后才 AC。

思路

首先，我们把所有位置和出口的距离算出来（用 BFS），记为 $d_{x,y}$，顺便求出离它最近的出口坐标，记为 $(X_{x,y},Y_{x,y})$。我们发现这个需要在队列里记下这个点的最近出口位置以及具体坐标。

然后我们像涟漪一样扩散着用 BFS 去求方向。找每个位置的上一步，然后判断是否是一条路上的（即最近出口相同且距离大于这个点的距离），如果是，那么修改方向并压入队列，否则忽略。

似乎很成功地做完了，那么有哪些易错点呢？

• 更新方向的时候一定要注意距离是否大于当前点的距离。注意：必须是严格大于，等于也不可以，因为加上这一步之后就不是最优。
• 记得把安全疏散出口的最近出口位置设为它自己。
• 一定要用 BFS，而不是 DFS，两个函数都得用 BFS。

代码

AC 提交记录：Submission #65683293。

TLE 提交记录：第一发、第二发、第三发。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;int h, w, d[1010][1010];
char a[1010][1010];
pair<int, int> p[1010][1010];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char cc[] = {'v', '^', '>', '<'};void work()
{queue<pair<pair<int, int>, pair<int, int> > > q;for (int x = 1; x <= h; x++)for (int y = 1; y <= w; y++)if (a[x][y] == 'E'){p[x][y] = make_pair(x, y);q.push(make_pair(make_pair(x, y), make_pair(x, y)));d[x][y] = 0;}while (q.size()){int fx = q.front().first.first;int fy = q.front().first.second;int xx = q.front().second.first;int yy = q.front().second.second;q.pop();for (int i = 0; i < 4; i++){int nx = fx + dx[i];int ny = fy + dy[i];if (nx < 1 || nx > h)continue;if (ny < 1 || ny > w)continue;if (a[nx][ny] != '.')continue;if (d[nx][ny] > d[fx][fy] + 1){d[nx][ny] = d[fx][fy] + 1;p[nx][ny] = make_pair(xx, yy);q.push(make_pair(make_pair(nx, ny), make_pair(xx, yy)));}}}
}void calc()
{queue<pair<int, int> > q;for (int x = 1; x <= h; x++)for (int y = 1; y <= w; y++)if (a[x][y] == 'E')q.push(make_pair(x, y));while (q.size()){int fx = q.front().first;int fy = q.front().second;q.pop();for (int i = 0; i < 4; i++){int nx = fx + dx[i];int ny = fy + dy[i];if (nx < 1 || nx > h)continue;if (ny < 1 || ny > w)continue;if (a[nx][ny] != '.')continue;if (p[nx][ny] != p[fx][fy])continue;if (d[nx][ny] <= d[fx][fy])continue;a[nx][ny] = cc[i];q.push(make_pair(nx, ny));}}
}int main()
{cin >> h >> w;for (int i = 1; i <= h; i++)for (int j = 1; j <= w; j++)cin >> a[i][j];memset(d, 0x3f, sizeof(d));work();calc();for (int i = 1; i <= h; i++){for (int j = 1; j <= w; j++)cout << a[i][j];cout << endl;}return 0;
}