题解：P14098 [POCamp 2022] 狼抓兔子 II / Djur

Egg_eating_master · 2025-10-02 10:44:10 · 题解

让第一个人尽量贴着他左边的墙壁走，第二个人尽量贴着他右边的墙壁走。

形式化地，让第一个人在决定下一步的方向时，依次尝试左转、直走、右转、回头；第二个人依次尝试右转、直走、左转、回头。

这样得到两条从 (1,1) 到 (n,m) 的路径，如果有交就无解，否则就输出。

时间复杂度 O(nm)。

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int n, m;
string s[maxn];
vector<int> a[maxn], b[maxn];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
bool heige(int p, vector<int> *a) {
    int x = 1, y = 1, q = p;
    while (x != n || y != m) {
        if (p != q && x == 1 && y == 1) return 0;
        a[x][y] = 1;
        bool fl = 0;
        for (int i = 3; i <= 6; i++) {
            int nx = x + dx[(p + i) % 4], ny = y + dy[(p + i) % 4];
            if (s[nx][ny] == '.') {x = nx, y = ny, p = (p + i) % 4; fl = 1; break;}
        }
        if (!fl) return 0;
    }
    return 1;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 0; i <= m + 1; i++) s[0] += "#", s[n + 1] += "#";
    for (int i = 1; i <= n; i++) s[i] = "#" + s[i] + "#";
    for (int i = 0; i <= n + 1; i++) a[i].resize(m + 2), b[i].resize(m + 2);
    if (!heige(0, a)) {cout << "NO" << '\n'; return 0;}
    reverse(dx, dx + 4); reverse(dy, dy + 4);
    if (!heige(2, b)) {cout << "NO" << '\n'; return 0;}
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue;
            if (a[i][j] && b[i][j]) {cout << "NO" << '\n'; return 0;}
        }
    a[1][1] = b[1][1] = 0;
    cout << "YES" << '\n';
    for (int i = 1; i <= n; i++, cout << '\n')
        for (int j = 1; j <= m; j++)
            if (a[i][j]) cout << 'V';
            else if (b[i][j]) cout << 'K';
            else cout << s[i][j];
    return 0;
}

::::