Submission #65684512

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

template <typename Tp>
struct Triplet {
    Tp x, y, z;
};

const int MAXN = 1e3 + 5, INF = 1e9 + 5,
mov[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char s[MAXN][MAXN],
arrow[] = {'^', 'v', '<', '>'};
int d[MAXN][MAXN];
queue<Triplet<int>> Q;

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int H, W;
    cin >> H >> W;
    for (int i = 1; i <= H; i ++) {
        for (int j = 1; j <= W; j ++) {
            cin >> s[i][j];
            if (s[i][j] != '.') {
                d[i][j] = INF;
            }
            if (s[i][j] == 'E') {
                Q.push({i, j, 0});
            }
        }
    }
    while (!Q.empty()) {
        auto [x, y, e] = Q.front();
        Q.pop();
        for (auto [u, v] : mov) {
            if (1 <= x + u && x + u <= H &&
                1 <= y + v && y + v <= W &&
                !d[x + u][y + v]) {
                d[x + u][y + v] = e + 1;
                Q.push({x + u, y + v, e + 1});
            }
        }
    }
    for (int i = 1; i <= H; i ++) {
        for (int j = 1; j <= W; j ++) {
            if (s[i][j] == '.') {
                for (int k = 0; k < 4; k ++) {
                    auto [u, v] = mov[k];
                    if (1 <= i + u && i + u <= H &&
                        1 <= j + v && j + v <= W &&
                        (d[i][j] > d[i + u][j + v] || s[i + u][j + v] == 'E')) {
                        s[i][j] = arrow[k];
                        break;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= H; i ++) {
        for (int j = 1; j <= W; j ++) {
            cout << s[i][j];
        }
        cout << '\n';
    }
    return 0;
}

Submission Info

Judge Result