この問題は 多始点 BFS(幅優先探索) をテーマとした問題です。

全ての通路マス \((i, j)\) について、最寄りの非常口との距離 \(d(i, j)\) を計算することを考えます。これは以下の手順で行うことができます。

• はじめ、すべてのマスについて\(d(i, j) = \infty\) とする。
• すべてのマスを走査して非常口のマス \((i, j)\) について \(d(i, j) = 0\) とする。
• 非常口のマスすべてを BFS の開始地点として BFS を行う。

また、BFS を行いながら各通路マスについて「そのマスに来る直前にどこのマスにいたか」に応じて通路マスに矢印を書き込んでいきます。このようにして書き込んだ矢印が問題文の条件を満たすことは最短経路の性質から従います。

以上の方法を適切に実装することで今回の問題を解くことができます。計算量は \(\mathrm{O}(HW)\) で十分高速です。

• 実装例(C++)

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  for (auto& s : S) cin >> s;

  queue<pair<int, int>> Q;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (S[i][j] == 'E') Q.emplace(i, j);
    }
  }
  int dx[] = {1, 0, -1, 0};
  int dy[] = {0, 1, 0, -1};
  auto ok = [&](int i, int j) { return 0 <= i and i < H and 0 <= j and j < W; };
  string A = "^<v>";
  while (!Q.empty()) {
    auto [i, j] = Q.front();
    Q.pop();
    for (int k = 0; k < 4; k++) {
      int ni = i + dx[k];
      int nj = j + dy[k];
      if (!ok(ni, nj)) continue;
      if (S[ni][nj] != '.') continue;
      S[ni][nj] = A[k];
      Q.emplace(ni, nj);
    }
  }

  for (auto& s : S) cout << s << "\n";
}