前言

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;
}