题解：P14299 [JOI2023 预选赛 R2] 填充 / Painting

· · 题解

题解：P14299 [JOI2023 预选赛 R2] 填充 / Painting

题目传送门

思路

考虑广搜。

显然是一道搜索题。考虑对于每个未访问的格子，用广搜遍历与其相邻并属于同种颜色的格子，标记这个格子属于这个连通块，用一个数组 id 即可实现。

然后搜索结束后，用两个数组来记录当前连通块的大小和这个连通块的颜色，记录颜色用 cnt 做数组下标。

对于每个格子，考虑记录它相邻的其他块的 id_{x,y}。遍历每个格子和四个方向，如果相邻格子属于不同的连通块，记录关系用集合来记录和去重。

最后，对每个连通块 R，考虑所有可能的染色方案，然后取最大值。

详细解释见代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=505;
int h,w,g[maxn][maxn],id[maxn][maxn],sz[maxn*maxn],col[maxn*maxn],cnt;
//g表示颜色，id表示每个格子是哪个颜色块的
//sz表示每个连通块的大小，col代表每个连通块的颜色 
set<int> adj[maxn*maxn];  // 用set去重，记录每个块相邻的块 
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//偏移量 
void bfs(int x,int y)
{
    int c=g[x][y];//当前颜色 
    queue<pair<int,int>> q;
    q.push({x,y});//访问到的节点坐标 
    id[x][y]=cnt;//标记连通块 
    int s=0;//块的大小 
    while(!q.empty())
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        s++;
        for(int d=0;d<4;d++)//四个方向偏移量，访问相邻格子 
        {
            int nx=x+dx[d],ny=y+dy[d];
            if(nx<1||nx>h||ny<1||ny>w) continue;//超边界的跳过 
            if(id[nx][ny]!=-1) continue;//访问过的 
            if(g[nx][ny]==c)//颜色相同，标记格子，推进队列 
            {
                id[nx][ny]=cnt;
                q.push({nx,ny});
            }
        }
    }
    sz[cnt]=s;//记录连通块的信息 
    col[cnt]=c;
    cnt++;//块数增加 
}
int ans;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>h>>w;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            cin>>g[i][j];
    memset(id,-1,sizeof(id));//初始未访问 
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            if(id[i][j]==-1)//未访问的格子bfs一遍 
                bfs(i,j);
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            int u=id[i][j];
            for(int d=0;d<4;d++)
            {
                int nx=i+dx[d],ny=j+dy[d];
                if(nx<1||nx>h||ny<1||ny>w) continue;
                int v=id[nx][ny];
                if(u!=v) adj[u].insert(v);//记录相邻关系 
            }
        }
    }
    for(int i=0;i<cnt;i++)
    {
        unordered_map<int,int> mp;
        for(set<int>::iterator it=adj[i].begin();it!=adj[i].end();it++)
        {
            int j=*it;
            if(col[j]!=col[i])
                mp[col[j]]+=sz[j];//考虑不同颜色的块 
        }
        for(unordered_map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
            ans=max(ans,sz[i]+it->second);//尝试染成各种颜色 
        ans=max(ans,sz[i]);//取最大值 
    }
    cout<<ans;//输出 
    return 0;
}