Submission #65666420

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n)     for(int i = 0; i < (int)(n); ++i)
#define RREP(i, n)    for(int i = (int)(n); i-- > 0;)
#define FOR(i, l, r)  for(int i = (int)(l); i < (int)(r); ++i)
#define RFOR(i, r, l) for(int i = (int)(r); i-- > (int)(l);)
#define ALL(v)        std::begin(v), std::end(v)
using llong = long long;
using vi    = std::vector<int>;
using vvi   = std::vector<vi>;
using pii   = std::pair<int, int>;
using namespace std;
constexpr int       INF  = 1e9;
constexpr long long LINF = 1e18;
constexpr double    EPS  = 1e-10;
constexpr int       MOD  = 998'244'353;
constexpr int       MOD2 = 1e9 + 7;

template <typename Type>
inline std::istream &operator>>(std::istream &is, std::vector<Type> &v) {
    for(auto &elem : v) is >> elem;
    return is;
}

template <typename Type>
inline std::ostream &operator<<(std::ostream &os, const std::vector<Type> &v) {
    for(auto iter = v.cbegin(); iter != v.cend(); ++iter) os << (iter == v.cbegin() ? "" : " ") << *iter;
    return os;
}

#ifdef DEBUG

#include "debug.hpp"

#else

#define debug(...) static_cast<void>(0)

#endif

template <typename Type>
std::vector<Type> table(std::size_t n, const Type &val) { return std::vector<Type>(n, val); }

template <typename... Args>
auto table(std::size_t n, const Args &...args) { return std::vector(n, table(args...)); }

template <typename Type>
bool chmin(Type &a, const Type &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

template <typename Type>
bool chmax(Type &a, const Type &b) {
    if(a >= b) return false;
    a = b;
    return true;
}

int main(){
    int h,w;
    cin>>h>>w;

    vector<string> vs(h);
    cin>>vs;

    vector<pii> e;
    REP(i,h)REP(j,w){
        if(vs[i][j]=='E'){
            e.emplace_back(i,j);
        }
    }

    constexpr std::pair<int, int> dydx4[] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    auto is_inner = [&](int y, int x) -> bool {
        return (0 <= y and y < h and 0 <= x and x < w);
    };

    auto &&dp=table(h,w,INF);
    queue<pii> que;
    for(auto [y,x]:e){
        dp[y][x]=0;
        que.emplace(y,x);
    }
    while(!que.empty()){
        auto &&[y,x]=que.front();
        que.pop();

        for(const auto &[dy,dx]:dydx4){
            const int ny=y+dy, nx=x+dx;
            if(!is_inner(ny,nx) or vs[ny][nx]=='#') continue;
            if(chmin(dp[ny][nx],dp[y][x]+1)) que.emplace(ny,nx);
        }
    }
    debug(dp);

    const string key="^<>v";
    REP(i,h)REP(j,w){
        if(vs[i][j]=='.'){
            REP(k,4){
                const auto &[dy,dx]=dydx4[k];
                const int ny=i+dy, nx=j+dx;
                if(!is_inner(ny,nx)) continue;
                if(dp[ny][nx]==dp[i][j]-1){
                    vs[i][j]=key[k];
                    break;
                }
            }
        }
    }

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

Submission Info

Judge Result