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

cp_zry · 2026-05-10 20:17:59 · 题解

考虑先猜后证。

注意到在一个大小为 2 \times 2 的矩阵里，如果有三个数相同，那么可以直接输出 No。

我们考虑用一个典型例子来证明。

10
11

左上角的 1 和右下角的 1 一定联通，这两个 1 所构造的矩阵中一定包含这个 0，所以可以输出 No。

因为输出 No 意味着至少一个矩阵有缺角，而在缺角里一定有一个 2 \times 2 的矩阵里有三个数相同，所以条件充分。

#include<bits/stdc++.h>
using namespace std;
bool a[505][505],b[505][505];
int n,m,inl;
void solve(){
    memset(b,0,sizeof(b));
    inl=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++){
        char ch;
        cin>>ch;
        a[i][j]=(ch-'0');
       }
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++) {
            int k=a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1];
            if(k==1||k==3) {cout<<"No\n";return ;}
        }
    }
    cout<<"Yes\n";
    return ;   
}
int main(){
    int T;
    cin>>T;
    while(T--) solve();
}