题解 | #明日DISCO#

思路

设棋盘二维数组 arr[i][j] 对于 $\forall~i,j$ ，有 $1\leqslant i,j \leqslant n+1$ 使得 $arr[i][j]=0$ ，那么就代表可行。那么有以下贪心策略成立：

数组 $arr[i][j] = 0$ 时，continue;。
数组 $arr[i][j]>0$ 且四个方向均小于 0，那么 $arr[i][j]$ 可以降为 0，否则不做处理。
数组 $arr[i][j]<0$ 且四个方向均大于 0，那么 $arr[i][j]$ 可以升为 0，否则不做处理。

最后判断每一个 $arr[i][j]$ 是否为 0，即能否通过操作，把所有内部格子都变成 0。

证明

如果一个格子 $(i,j)$ 满足 $a_{i,j} > 0$ 且所有邻居 $\leqslant 0$ ，则它严格大于所有邻居（因为邻居 $\leqslant 0 < a_{i,j}$ ）。因此，操作1（减少1）始终适用，并且每减少一次，它仍然大于所有邻居（直到变为0）。连续执行操作1不会影响其他格子的操作条件，因为减少 $(i,j)$ 只会使其可下降到邻居的相对值增大，也就是说不会下降到邻居最大高度，不会破坏任何邻居的可操作条件。

负数区域完全对称。

如果邻居正负交替，该区域中心无论从下降还是上升，均不可能为 0（下降到最大整数，上升到最小负数），且不会影响邻居的操作条件。

Code

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

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

    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < n + 1; j++)
        {

            if (max({table[i - 1][j], table[i + 1][j], table[i][j - 1], table[i][j + 1]}) <= 0 &&
                table[i][j] >= 0)
            {
                table[i][j] = 0;
            }
        }
    }
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < n + 1; j++)
        {
            if (min({table[i - 1][j], table[i + 1][j], table[i][j - 1], table[i][j + 1]}) >= 0 &&
                table[i][j] <= 0)
            {
                table[i][j] = 0;
            }
        }
    }
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < n + 1; j++)
        {
            if (table[i][j] != 0)
            {
                cout << "NO";
                return 0;
            }
        }
    }
    cout << "YES";
    return 0;
}