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

· · 题解

求点赞 qwq！

赛时还在用 bfs 的我被气死了。

题意

判断所有同色连通块是否是矩形，是输出 Yes，否则输出 No。

思路

解法一

考虑什么情况下答案是 Yes。

显然对于网格纸上所有 2\times2 的子矩形，若全是同色，或者两个 0 两个 1，判 Yes。

因为当答案为 Yes 时，只可能出现这些情况。

反之，对于网格纸上每一个 2\times 2 的子矩形，子矩形里 3 同色 1 异色，连通块必然形成凹角或者不规则形状，绝对不是矩形，答案是 No：

即如果网格中存在任意一个 2\times 2 的子矩形，里面恰好有 1 个 0 或者恰好有 1 个 1，就输出 No。

解法二

求连通块用 bfs，求出来看看是否是矩形。

bfs 搜一个连通块时，给这个连通块染一样的色，记录该连通块的最小行、最大行、最小列、最大列，搜完这个连通块的时候看看最小最大行和最小最大列构成的矩形是否全是一样的色即可。

代码

两个的时间复杂度都是 O(n^2)。

:::success[解法一]{open}

#include<bits/stdc++.h>
using namespace std;
const int N=501;
int T,n,m;
string s[N];
bool f;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m,f=0;
        for(int i=1;i<=n;i++)cin>>s[i],s[i]=" "+s[i];
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                int tot=(s[i][j]==48)+(s[i+1][j]==48)+(s[i][j+1]==48)+(s[i+1][j+1]==48);
                if(tot==1||tot==3)f=1;
            }
        }
        cout<<(f?"No\n":"Yes\n");
    }
}

:::

:::success[解法二]

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int T,n,m,dx[]={-1,1,0,0},dy[]={0,0,-1,1};
string g[N];
bool vis[N][N];
bool check(int x,int y){
    char col=g[x][y];
    int mir=x,mxr=x,mic=y,mxc=y;
    queue<pair<int,int>> q;
    q.push({x,y}),vis[x][y]=1;
    while(!q.empty()){
        auto [u,v]=q.front();q.pop();
        mir=min(mir,u),mxr=max(mxr,u),mic=min(mic,v),mxc=max(mxc,v);
        for(int d=0;d<4;d++){
            int nu=u+dx[d],nv=v+dy[d];
            if(nu>=1&&nu<=n&&nv>=1&&nv<=m&&!vis[nu][nv]&&g[nu][nv]==col)vis[nu][nv]=1,q.push({nu,nv});
        }
    }
    for(int i=mir;i<=mxr;i++){
        for(int j=mic;j<=mxc;j++){
            if(g[i][j]!=col)return 0;
        }
    }
    return 1;
}
void sol(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>g[i];
        g[i]=" "+g[i];
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!vis[i][j]){
                if(!check(i,j)){
                    cout<<"No\n";
                    return;
                }
            }
        }
    }
    cout<<"Yes\n";
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>T;
    while(T--)sol();
}

:::