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

· · 题解

原来这个题应该叫做 vibrant / square 的，但是负责人说要让前六题名字整齐一点，所以起了个中文名。

给定一个 01 矩阵，问每个同色连通块是否均为矩形。

首先可以通过搜索完成本题。具体的，对于每个连通块，找出其所有点中所在行中的最上方行与最下方行，以及所在列中的最左侧列与最右侧列。接着遍历这四条直线在网格中围成的矩形，判断是否矩形中的所有数都相同。若全部相同，则该连通块为矩形，否则该连通块不为矩形。若找到一个不为矩形的连通块，直接输出 No 并进入下一组测试用例，否则继续检查其它连通块。若所有连通块都符合要求，输出 Yes。需要注意的是，若不在找到不为矩形的连通块时不直接输出 No，会导致复杂度从 O(nm) 退化为 O(nm \min\{n,m\})，不过仍然可以通过本题。

::::success[参考实现]

#include<bits/stdc++.h>
using namespace std;
const int Maxn=2000,Maxm=2000;
int T,n,m;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
string s;
bitset<Maxn+10> nums[Maxm+10],vis[Maxm+10];
queue<pair<int,int> > q;
void solve()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        for(int j=0;j<m;j++)
            nums[i][j]=s[j]-'0';
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            vis[i][j]=false;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(vis[i][j]) continue;
            int mnx=i,mxx=i,mny=j,mxy=j;
            vis[i][j]=true;
            q.push({i,j});
            while(!q.empty())
            {
                int ux=q.front().first,uy=q.front().second;
                mnx=min(mnx,ux),mxx=max(mxx,ux);
                mny=min(mny,uy),mxy=max(mxy,uy);
                q.pop();
                for(int k=0;k<4;k++)
                {
                    int vx=ux+dx[k],vy=uy+dy[k];
                    if(vx<0||vx>=n||vy<0||vy>=m) continue;
                    if(vis[vx][vy]) continue;
                    if(nums[vx][vy]!=nums[i][j]) continue;
                    vis[vx][vy]=true;
                    q.push({vx,vy});
                }
            }
            for(int k=mnx;k<=mxx;k++)
                for(int l=mny;l<=mxy;l++)
                    if(nums[k][l]!=nums[i][j])
                    {
                        cout<<"No\n";
                        return;
                    }
        }
    cout<<"Yes\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>T;
    while(T--)
        solve();
    return 0;
}

::::

除此之外，也有一些更为简便的做法。例如，考虑一个最左侧列为 l，最右侧列为 r，最下方行为 d 的其中所有数都相同的矩形下方一行。若该行中存在与其中相同的数字，则该连通块为矩形仅当 d+1 行的 l 到 r 列的所有数字全部与矩形中的数字相同。据此，可以推出每一行相较于上一行必然全部相同或全部相反，根据这一条件判断即可。时间复杂度为 O(nm)。

::::success[参考实现]

#include<bits/stdc++.h>
using namespace std;
const int Maxn=2000,Maxm=2000;
int T,n,m;
string s;
bitset<Maxn+10> nums[Maxm+10];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            cin>>s;
            for(int j=0;j<m;j++)
                nums[i][j]=s[j]-'0';
        }
        bool flag=true;
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++)
                if(nums[i][j]!=(nums[i-1][0]^nums[i-1][j]^nums[i][0])) flag=false;
        if(flag) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

::::

另外，也可以注意到若存在不为矩形的连通块，该连通块内必然存在 L 形，即在一个 2 \times 2 的子区域中恰好占据 3 格。根据此条件遍历所有的 2\times 2 的子区域判断亦可。时间复杂度为 O(nm)。

::::success[参考实现]

#include<bits/stdc++.h>
using namespace std;
const int Maxn=2000,Maxm=2000;
int T,n,m;
string s;
bitset<Maxn+10> nums[Maxm+10];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            cin>>s;
            for(int j=0;j<m;j++)
                nums[i][j]=s[j]-'0';
        }
        bool flag=true;
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++)
                if(nums[i][j]!=(nums[i-1][j-1]^nums[i-1][j]^nums[i][j-1])) flag=false;
        if(flag) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

::::