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

· · 题解

这题需要考虑怎么规避 vis 数组带来的 n^2 的时间复杂度。\ \ 我们发现每个点在搜索时只会被访问一次，但我们查看和初始化 vis 数组的时间复杂度我们都是不能接受的。我们就可以用一个 map 数组来存本次被访问到的节点，这样时间复杂度从线性复杂度降到了对数复杂度。我们考虑记录我们访问节点的左上角和右下角，然后依次访问 map 确定以这两点为两角的矩形是否全被访问到。若有没被访问到的就不是矩形。\ \ 但是访问的节点可能比这个矩形多，我们该怎么处理呢？我们可以记录访问的点的个数，若这个数比那个矩形的面积大则说明这个格不是矩形。由于上一操作保证了这个数一定不小于这个矩形的面积，我们就可以放心大胆地这么做。\ \ 但每组测试数据开始是我们仍需初始化 vis 数组，极限下是 t\times n\times m 次运算，我们可能接受不了，所以我们考虑使用 bitset 的 reset() 函数以减小 64 倍的常数。实际运行结果很优秀。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,t,num;
bitset<510>vis[510];
char c[510][510];
map<pair<int,int>,bool>mp;
pair<int,int>minn={111111,111111},maxn={0,0};
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
void dfs(int x,int y,int color){
    num++;
    mp[{x,y}]=1;vis[x][y]=1;
    minn=min(minn,{x,y});
    maxn=max(maxn,{x,y});//一定要在开始时记录信息，不然可能忘记记录初始点
    for(int d=0;d<4;d++){
        int nx=x+dx[d],ny=y+dy[d];
        if(vis[nx][ny]||nx<1||nx>n||ny<1||ny>m)continue;
        if(c[nx][ny]!=color+'0')continue;
        dfs(nx,ny,color);
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        for(int i=1;i<=502;i++)vis[i].reset();
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>c[i][j];
            }
        }
        bool ok=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(!vis[i][j]){
                    num=0;minn={111111,111111};maxn={0,0};
                    mp.clear();//一定要初始化足够多的变量
                    dfs(i,j,c[i][j]=='1'?1:0);
                    for(int ii=minn.first;ii<=maxn.first;ii++){
                        for(int jj=minn.second;jj<=maxn.second;jj++){
                            if(mp.find({ii,jj})==mp.end()){
                                ok=1;break;//遍历矩形
                            }
                        }
                        if(ok)break;
                    }
                    if(ok){
                        cout<<"No";
                        break;
                    }
                    if(num!=(maxn.second-minn.second+1)*(maxn.first-minn.first+1)){//计算实际访问点数是否过多。
                        ok=1;cout<<"no";break;
                    }
                }
            }
            if(ok)break;
        }
        if(!ok)cout<<"Yes";
        cout<<"\n";
    }
    return 0;
}