题目 G. X 光环 详细题解

问题重述

有一个 $R$ 行 $C$ 列的网格，每个格子 $(r,c)$ 有一个高度 $H_{r,c} \in \{0,\dots,9\}$。移动规则：从 $(r,c)$ 可以走到相邻的四个格子（上下左右），代价为 $(h_1 - h_2)^X$，其中 $X$ 是一个奇数正整数（$1 \le X \le 9$）。注意代价可以为负。
给定 $Q$ 个查询，每个询问从起点 $(R_s,C_s)$ 到终点 $(R_f,C_f)$ 的最小总代价。若存在一条路径使得总代价可以任意小（即存在负环），则输出 INVALID；否则输出最小总代价。

关键性质

由于 $X$ 是奇数，函数 $f(d)=d^X$ 是奇函数：

因此，沿一条边正向和反向的代价互为相反数。这导致沿着任何环的代价具有反对称性。

零环条件

定义环的总代价为沿环走一圈的代价之和。若所有环的总代价均为 $0$，则称该网格是零环的。

引理 1：网格是零环的当且仅当每个 $2\times 2$ 子网格（即由相邻两行两列构成的四个格子）的环代价为 $0$。

证明：任意环都可以分解为若干个 $2\times 2$ 基本环的线性组合。因此，若所有 $2\times 2$ 环的代价为零，则所有环的代价为零；反之，若存在一个 $2\times 2$ 环的代价非零，则它本身就是一个非零环。由于奇函数性质，该环的代价要么为正要么为负，取其反向即可得到负环。$\square$

因此，判断整个网格是否存在负环（即是否存在总代价可以任意小的路径）等价于检查是否存在一个 $2\times 2$ 子网格，其四个边按顺时针方向的代价之和不为 $0$。

无负环时的最短路径

若所有 $2\times 2$ 子网格的环代价均为 $0$，则网格是零环的。此时，任意两点之间的路径代价与路径无关，只取决于起点和终点。更具体地，存在一个势能函数 $\phi(r,c)$，使得从 $u$ 到 $v$ 的任意路径的代价等于 $\phi(v)-\phi(u)$。这可以通过以下事实得出：

• 由零环条件，对任意三点 $u,v,w$ 有 $d(u,v)+d(v,w)+d(w,u)=0$，从而 $d(u,v) = -d(v,u)$ 且 $d(u,v)=d(u,w)+d(w,v)$。
• 固定一个参考点 $s$（例如 $(1,1)$），定义 $\phi(u)=d(s,u)$。则 $d(u,v)=\phi(v)-\phi(u)$。

因此，只需计算出从 $s$ 到所有格子的代价 $\phi$，即可在 $O(1)$ 时间内回答每个查询：

计算 $\phi$ 的方法

由于所有环代价为零，从 $s$ 到任意格子的任意路径的代价都相同。因此，我们可以通过一次广度优先搜索（BFS）或深度优先搜索（DFS）来得到 $\phi$。具体做法：

• 初始化 $\phi(s)=0$，用一个队列存储已访问的格子。
• 从队列中取出格子 $u$，对它的四个邻居 $v$，若 $v$ 未访问，则计算$$\phi(v) = \phi(u) + (H_u - H_v)^X$$ 并将 $v$ 入队。
• 因为所有路径代价相等，第一次访问时得到的 $\phi(v)$ 就是正确的，后续不会再被更新。

整个遍历过程 $O(RC)$，因为每个格子只入队一次，每条边只被考虑一次。

算法步骤总结

1. 读入 $R,C,X$ 以及高度矩阵 $H$。
2. 检查所有 $2\times 2$ 子网格（$1\le i<R$，$1\le j<C$），计算$$\text{cycle} = (H_{i,j}-H_{i,j+1})^X + (H_{i,j+1}-H_{i+1,j+1})^X + (H_{i+1,j+1}-H_{i+1,j})^X + (H_{i+1,j}-H_{i,j})^X $$若存在某个 $\text{cycle} \neq 0$，则标记整个网格为无效（存在负环）。
3. 若无效，则对于所有查询输出 INVALID。
4. 否则，进行 BFS 从 $(1,1)$ 出发计算 $\phi$ 数组。
5. 对于每个查询 $(R_s,C_s,R_f,C_f)$，输出 $\phi(R_f,C_f) - \phi(R_s,C_s)$。

复杂度分析

• 检查 $2\times 2$ 子网格：$O(RC)$。
• BFS 遍历：$O(RC)$。
• 每个查询：$O(1)$。
• 总时间复杂度 $O(RC + Q)$，空间 $O(RC)$。满足 $R,C \le 1000$，$Q \le 10^5$ 的限制。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll pow_odd(ll base, int exp) {
    ll res = 1;
    for (int i = 0; i < exp; ++i) res *= base;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int R, C, X;
    cin >> R >> C >> X;
    vector<string> H(R);
    for (int i = 0; i < R; ++i) cin >> H[i];
    
    // 检查所有 2x2 子网格是否零环
    bool invalid = false;
    for (int i = 0; i < R - 1; ++i) {
        for (int j = 0; j < C - 1; ++j) {
            int a = H[i][j] - '0';
            int b = H[i][j+1] - '0';
            int c = H[i+1][j+1] - '0';
            int d = H[i+1][j] - '0';
            ll cycle = pow_odd(a - b, X) + pow_odd(b - c, X) + 
                       pow_odd(c - d, X) + pow_odd(d - a, X);
            if (cycle != 0) {
                invalid = true;
                break;
            }
        }
        if (invalid) break;
    }
    
    if (invalid) {
        int Q;
        cin >> Q;
        while (Q--) {
            int rs, cs, rf, cf;
            cin >> rs >> cs >> rf >> cf;
            cout << "INVALID\n";
        }
        return 0;
    }
    
    // BFS 计算势能
    vector<vector<ll>> phi(R, vector<ll>(C, 0));
    vector<vector<bool>> vis(R, vector<bool>(C, false));
    queue<pair<int,int>> q;
    q.push({0,0});
    vis[0][0] = true;
    phi[0][0] = 0;
    int dr[] = {1, -1, 0, 0};
    int dc[] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto [r,c] = q.front(); q.pop();
        int h1 = H[r][c] - '0';
        for (int d = 0; d < 4; ++d) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            if (vis[nr][nc]) continue;
            int h2 = H[nr][nc] - '0';
            phi[nr][nc] = phi[r][c] + pow_odd(h1 - h2, X);
            vis[nr][nc] = true;
            q.push({nr, nc});
        }
    }
    
    int Q;
    cin >> Q;
    while (Q--) {
        int rs, cs, rf, cf;
        cin >> rs >> cs >> rf >> cf;
        --rs; --cs; --rf; --cf;
        cout << phi[rf][cf] - phi[rs][cs] << '\n';
    }
    return 0;
}

样例验证

以样例1为例，$X=1$，所有 $2\times 2$ 子网格的环代价均为 $0$，计算势能后得到查询结果与输出一致。
样例2中存在非零 $2\times 2$ 子网格，因此所有查询输出 INVALID。
样例3中 $X=9$，同样无负环，输出正确。

本题的关键在于识别零环条件与势能函数的线性性质，从而将复杂的图论问题简化为简单的网格遍历。