题解：P16439 [XJTUPC 2026] 鲜艳 / 方格

zhouhuan2013 · 2026-05-11 19:05:37 · 题解

题目传送门

看到题解区一半的题解都是用 dfs 或 bfs 实现的，说实话这题真的不用那么麻烦。

认真读一下题目可以发现，它就是要求我们去判断网格中所有 0 或 1 的连通块都必须是实心矩形。

经过样例的分析我们可以轻松地推出一个结论，如果网格满足任意一个 2 \times 2 的小正方形中，不会出现恰好 3 个相同颜色或 1 个不同颜色的情况，那么所有连通块都都会是矩形。

下面给出代码。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,n,m,a[505][505];
    char pd;
    cin>>T;
    while(T--){
        // 标记是否合法，记得初始化
        bool bj=1;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>pd;
                // 把字符转成整数
                a[i][j]=pd-48;
            }
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                // 计算正方形内四个数字的和
                int p=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
                // 如果和为 1 或 3，就不合法
                if(p==1||p==3)
                    bj=0;
            }
        }
        if(bj)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}