题解 P9351【[JOI 2023 Final] Maze】

0x3F · 2024-06-12 17:23:38 · 题解

注意到，如果我们现在处于 (x,y)，则我们可以花费 1 单位的代价，到达以 (x,y) 为中心的，边长为 2N+1 的正方形区域内的任意一个格子（四个角除外）。若 (x,y) 为白格，则还可以不花费任何代价，到达与 (x,y) 四连通的格子。

其中第一种移动方式还可以拆分成一次向四连通格子移动和 N-1 次向八连通格子移动。我们可以添加高度维，等价转化为以下模型：

初始时位于起点，高度为 0。

若当前高度为 0 且位于白格，则可以不花费任何代价，向四连通格移动，高度仍为 0。

若当前高度为 0 且位于黑格，则可以花费 1 单位的代价，向四连通格移动，并且高度变为 N-1。

若当前高度不为 0，则可以不花费任何代价，向八连通格移动，高度减少 1。

问需要多少代价到达终点，高度不限。

我们以代价（从小到大）为第一关键字，高度（从高到低）为第二关键字，跑 01 BFS 即可。

时间复杂度为 \mathcal{O}(rc)。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
const int _ = 6e6 + 10;
int n, m, k, sx, sy, tx, ty;
bool arr[_], vis[_];
inline bool check(int x, int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}
inline int id(int x, int y) {
    return (x - 1) * m + y;
}
struct node {
    int x, y, t, h;
};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    cin >> sx >> sy;
    cin >> tx >> ty;
    for (int i = 1; i <= n; i++) {
        string str;
        cin >> str;
        for (int j = 1; j <= m; j++) {
            arr[id(i, j)] = (str[j-1] == '#');
        }
    }
    deque<node> Q(1, (node){sx, sy, 0, 0});
    while (true) {
        node N = Q.front();
        Q.pop_front();
        int x = N.x;
        int y = N.y;
        int t = N.t;
        int h = N.h;
        if (vis[id(x, y)]) continue;
        vis[id(x, y)] = true;
        if (x == tx && y == ty) {
            cout << t << endl;
            return 0;
        }
        if (h) {
            for (int d = 0; d <= 7; d++) {
                int xx = x + dx8[d];
                int yy = y + dy8[d];
                if (check(xx, yy) && !vis[id(xx, yy)]) {
                    Q.push_back((node){xx, yy, t, h-1});
                }
            }
        } else {
            for (int d = 0; d <= 3; d++) {
                int xx = x + dx4[d];
                int yy = y + dy4[d];
                if (check(xx, yy) && !vis[id(xx, yy)]) {
                    if (arr[id(xx, yy)]) {
                        Q.push_back((node){xx, yy, t+1, k-1});
                    } else {
                        Q.push_front((node){xx, yy, t, 0});
                    }
                }
            }
        }
    }
}