Submission #37386657

---

Source Code Expand

// JOI2022/2023 二次予選 C - 塗りつぶし (Painting)
#include <bits/stdc++.h>
using namespace std;

//それぞれ、こんな感じに短縮しています…！
using ll = long long;
#define ALL(a)  (a).begin(),(a).end()
using v_vll = vector<vector<ll>>;
//

//4近傍の座標の差分をひとまとめにしました！
vector<ll> di={1,0,-1,0};
vector<ll> dj={0,-1,0,1};
//

ll H,W;
ll connected_componets_size=0;//連結成分に含まれるマスの数
v_vll reference_nums;//各連結成分に振られた整理番号をマスごとに保持する
v_vll A;//与えられた盤面を保持する
ll assigned_refernce_number=0;//現在割り当て中の整理番号
//(DFSをする前に毎度インクリメントするので実際には1からはじまります)
void DFS(ll nowi,ll nowj,ll wanted_color){
    if(reference_nums[nowi][nowj]>0){return ;}
    else{
        connected_componets_size++;
        reference_nums[nowi][nowj]=assigned_refernce_number;
        for(ll i=0;i<4;i++){
            if(1<= nowi+di[i] and nowi+di[i]<=H and 1<=nowj+dj[i] and nowj+dj[i]<=W){
                //移動先が範囲内ならば…移動先の色を調べる
                if(A[nowi+di[i]][nowj+dj[i]]==wanted_color){
                    DFS(nowi+di[i],nowj+dj[i],wanted_color);
                }
            }
        }
        return ;
    }
}

vector<vector<bool>> visited;
v_vll graph;
//visitedは無限ループに陥るのを防ぐための目印
//graphでは、各連結成分の隣接関係を管理する
void DFS_2(ll nowi,ll nowj,ll ref_num){
    //ref_num:現在注目中の連結成分に割り振られた整理番号
    //(reference_numberはながいので)
    if(visited[nowi][nowj]==true){return ;}
    else{
        visited[nowi][nowj]=true;
        for(ll i=0;i<4;i++){
            if(1<= nowi+di[i] and nowi+di[i]<=H and 1<=nowj+dj[i] and nowj+dj[i]<=W){
                    //移動先が範囲内ならば
                    //移動先の整理番号を調べる
                    if(reference_nums[nowi+di[i]][nowj+dj[i]]==ref_num){
                        //移動先のマスの整理番号が注目中のマスのものに等しければ
                        DFS_2(nowi+di[i],nowj+dj[i],ref_num);
                    }
                    else{
                        //隣接する連結成分として登録！
                        graph.at(ref_num).push_back(reference_nums[nowi+di[i]][nowj+dj[i]]);
                    }
                }
        }
        return ;
    }
}
int main(){
    cin>>H>>W;
    reference_nums.resize(H+1);
    for(ll i=1;i<=H;i++){
        reference_nums.at(i).resize(W+1,-1);
    }
    A.resize(H+1);
    for(ll i=1;i<=H;i++){
        A.at(i).resize(W+1);
    }
    for(ll i=1;i<=H;i++){
        for(ll j=1;j<=W;j++){
            cin>>A[i][j];
        }
    }
    //Part.1 START>>
    map<ll,pair<ll,ll>> color_and_quantity;
    map<ll,pair<ll,ll>> representatives;
    for(ll i=1;i<=H;i++){
        for(ll j=1;j<=W;j++){
            if(reference_nums[i][j]>0){continue;}
            else{
                connected_componets_size=0;
                assigned_refernce_number++;
                DFS(i,j,A[i][j]);
                color_and_quantity[assigned_refernce_number]={A[i][j],connected_componets_size};
                representatives[assigned_refernce_number]={i,j};
            }
        }
    }
    //<<Part1.END
    
    //Part2.START>>
    visited.resize(H+1);
    graph.resize(assigned_refernce_number+1);//連結成分の数だけ、ドラマがある
    for(ll i=1;i<=H;i++){//visitedの初期化
        visited.at(i).resize(W+1,0);
    }
    for(ll i=1;i<=assigned_refernce_number;i++){
        pair<ll,ll> coord=representatives[i];
        DFS_2(coord.first,coord.second,i);
    }
    for(ll i=1;i<=assigned_refernce_number;i++){
        //隣接リストのうち、重複しているものは削除。これでもなぜか間に合います
        sort(ALL(graph[i]));
        graph[i].erase(unique(graph[i].begin(), graph[i].end()), graph[i].end());
    }
    //<<Part2.END

    //Part3.START>>
    ll ans=0;
    ll looking;//現在注目中の連結成分のマスの数
    for(ll i=1;i<=assigned_refernce_number;i++){
        looking=color_and_quantity[i].second;
        map<ll,ll> surrounding_color_and_quantity;//隣接する連結成分に含まれるマスの色と、その合計の数
        for(ll a:graph[i]){
            surrounding_color_and_quantity[color_and_quantity[a].first]+=color_and_quantity[a].second;
            //<補足>
            //color_and_quantity[a].first:整理番号aの連結成分の色
            //color_and_quantity[a].second:整理番号aの連結成分のマスの数
        }   
        ll maxel=0;//max_element
        for(auto b:surrounding_color_and_quantity){
            maxel=max(maxel,b.second);
        }
        ans=max(ans,maxel+looking);
    }
    cout<<ans<<endl;
    //おつかれさまでした！！
}

Submission Info

Judge Result