题解：AT_abc405_d [ABC405D] Escape Route

Hyh_111 · 2025-05-14 13:03:36 · 题解

思路

以每个紧急出口为起点做 BFS，在到达每个点时，根据到达之前的点的方向在答案数组中写入对应的箭头。

代码：

#include <bits/stdc++.h>
#define int long long
//#define USE_FREOPEN
//#define MUL_TEST
#define FILENAME ""
using namespace std;
constexpr int N = 5005, M = 5005;
int dx[4] = {0, 1, 0, -1}; 
int dy[4] = {1, 0, -1, 0}; 
char da[4] = {'<', '^', '>', 'v'}; //各个方向对应箭头
char mp[N][M],ans[N][M];
bool vis[N][M];
queue<pair<int, int> > q;

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
            if (mp[i][j] == 'E') { //将每个紧急出口加入队列
                q.push(make_pair(i, j));
                vis[i][j] = 1;
            }
            ans[i][j] = mp[i][j];
        }
    }

    while (q.size()) { //BFS
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx <= 0 || tx > n || ty <= 0 || ty > m || mp[tx][ty] == '#' || vis[tx][ty]) continue; //判边界、墙和已走过的位置
            q.push(make_pair(tx, ty));
            vis[tx][ty] = 1;
            ans[tx][ty] = da[i]; //写入答案
        }
    }

    //输出答案
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cout << ans[i][j];
        cout << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    #ifdef USE_FREOPEN
        freopen(FILENAME ".in","r",stdin);
        freopen(FILENAME ".out","w",stdout);
    #endif
    int _ = 1;
    #ifdef MUL_TEST
        cin >> _;
    #endif
    while (_--)
        solve();
    _^=_;
    return 0^_^0;
}