题解 | #明日DISCO#

这是一个经典的网格操作与稳定性分析问题。我们可以通过分析操作的性质、状态的单调性以及“死锁”条件来得出一个基于贪心策略或事件驱动模拟的算法。

问题分析

我们需要判断是否可以通过有限次操作将整个网格的所有数值变为 0。操作规则是：局部最大值可以减小，局部最小值可以增加。这实际上是一个能量最小化或平滑化的过程（类似于山峰被侵蚀，山谷被填平）。

关键性质：

目标唯一性：由于边界固定为 0，且我们希望平滑后的结果所有值相等，因此唯一可能的目标状态就是全 0 矩阵。
操作的可逆性与汇合性：该系统具有汇合性（类似于阿贝尔沙堆模型或芯片均分游戏）。如果存在一个操作序列能到达全 0 状态，那么任意合法的操作序列执行下去，最终结果都是一样的。也就是说，我们不需要担心“当前这一步该选哪个格子操作”，只要能操作就操作，最终结果是注定的。
操作的“死锁”与瓶颈：如果在某个非全 0 的状态下，没有任何一个格子是“严格大于所有邻居”或“严格小于所有邻居”的，那么系统就陷入了“死锁”（Deadlock）。死锁的典型特征是存在相邻的相等数值（Plateau），例如 5, 5。在 5, 5 的状态下，左边的 5 不大于右边的 5，右边的 5 也不大于左边的 5，导致两者都无法下降。

算法

该问题不能通过简单的数学公式（如奇偶校验或求和）直接判断，因为操作的顺序和数值的大小紧密相关。最稳妥且符合复杂度要求的方法是模拟收敛过程。关键在于利用“跳跃式更新”（直接变为邻居的最值）来替代“一步步加减 1”，从而避免超时。

由于可以跳过中间的微小步骤（例如从 100 减到 50，中间不需要一步步模拟），我们可以使用事件驱动的模拟（Event-Driven Simulation）。对于一个局部最大值 $a_{x,y}$ ，它的数值可以安全地、一次性地降低到其邻居中的最大值（因为在它降低到邻居最大值之前，它一直保持着局部最大值的性质）。同理，局部最小值可以一次性提升到邻居中的最小值。我们不断重复这个“削峰填谷”的过程，直到网格不再变化。最后检查网格是否全为 0。

时间与空间复杂度分析

空间复杂度： $O(n^2)$
- 需要存储 $n \times n$ 的网格以及一个队列。
时间复杂度：
- 每次操作会将一个格子的值修改为邻居的数值。
- 这就是一个在有向无环图（DAG）或者势能下降表面上的最短路径/传播问题。
- 每个格子 $a_{x,y}$ 的值只会单调递减（如果是正数）或单调递增（如果是负数），且每次变化至少会“对齐”到一个邻居的值。这种“对齐”操作类似于 Dijkstra 算法中的松弛操作（Relaxation）。
- 在最坏情况下，一个值的改变会像波浪一样传播过整个网格。总的操作次数大致与网格的边数相关，即每个节点入队出队的次数是有限的常数次（平均）或与 $n$ 线性相关。
- 综合评估，这种事件驱动的复杂度接近 $O(n^3)$ 或更优（取决于数据的平滑程度，通常接近 $O(n^2 \log n)$ 或 $O(n^2)$ ）。

代码实现

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

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

    int n;
    cin >> n;
    vector<vector<ll>> a(n + 2, vector<ll>(n + 2, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }

    queue<pii> Q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j] > a[i - 1][j] && a[i][j] > a[i + 1][j] && a[i][j] > a[i][j + 1] &&
                    a[i][j] > a[i][j - 1]) {
                Q.push({i, j});
                continue;
            }
            if (a[i][j] < a[i - 1][j] && a[i][j] < a[i + 1][j] && a[i][j] < a[i][j + 1] &&
                    a[i][j] < a[i][j - 1]) {
                Q.push({i, j});
            }
        }
    }

    while (!Q.empty()) {
        auto [i, j] = Q.front();
        Q.pop();
        if (a[i][j] > a[i - 1][j] && a[i][j] > a[i + 1][j] && a[i][j] > a[i][j + 1] &&
                a[i][j] > a[i][j - 1]) {
            a[i][j] = max(a[i - 1][j], max(a[i + 1][j], max(a[i][j + 1], a[i][j - 1])));
        }
        if (a[i][j] < a[i - 1][j] && a[i][j] < a[i + 1][j] && a[i][j] < a[i][j + 1] &&
                a[i][j] < a[i][j - 1]) {
            a[i][j] = min(a[i - 1][j], max(a[i + 1][j], max(a[i][j + 1], a[i][j - 1])));
        }
    }

    for (int i = 0; i < n + 2; i++) {
        for (int j = 0; j < n + 2; j++) {
            if (a[i][j] != 0) {
                cout << "NO\n";
                return 0;
            }
        }
    }
    cout << "YES\n";
    return 0;
}