寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #E - ペンキの色

第7回日本情報オリンピック 本選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#E - ペンキの色

https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=11

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#E - ペンキの色
https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=11
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int main(void){
  ll h,w;
  cin>>h>>w;
  vector<ll> x{0,h},y{0,w};
  ll n;
  cin>>n;
  vector<ll> a(n),b(n),c(n),d(n);
  for(ll i=0;i<n;i++){
    cin>>a[i]>>b[i]>>c[i]>>d[i];
    x.push_back(a[i]);
    y.push_back(b[i]);
    x.push_back(c[i]);
    y.push_back(d[i]);
  }
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  x.erase(unique(x.begin(),x.end()),x.end());
  y.erase(unique(y.begin(),y.end()),y.end());
  h=x.size();
  w=y.size();
  map<ll,ll> mpx,mpy;
  for(ll i=0;i<h;i++){
    mpx[x[i]]=i;
  }
  for(ll i=0;i<w;i++){
    mpy[y[i]]=i;
  }
  vector<vector<ll>> r(h,vector<ll>(w));
  for(ll i=0;i<n;i++){
    r[mpx[a[i]]][mpy[b[i]]]++;
    r[mpx[a[i]]][mpy[d[i]]]--;
    r[mpx[c[i]]][mpy[b[i]]]--;
    r[mpx[c[i]]][mpy[d[i]]]++;
  }
  h--;
  w--;
  for(ll i=0;i<h;i++){
    for(ll j=0;j<w;j++){
      r[i+1][j]+=r[i][j];
      r[i][j+1]+=r[i][j];
      r[i+1][j+1]-=r[i][j];
    }
  }
  ll ans=0;
  for(ll i=0;i<h;i++){
    for(ll j=0;j<w;j++){
      if(r[i][j]){
        continue;
      }
      queue<pair<ll,ll>> q;
      q.push({i,j});
      ans++;
      r[i][j]=1;
      while(!(q.empty())){
        auto[x,y]=q.front();
        q.pop();
        for(ll k=0;k<4;k++){
          ll nx=x+dx[k];
          ll ny=y+dy[k];
          if((0<=nx && nx<h) && (0<=ny && ny<w) && !r[nx][ny]){
            r[nx][ny]=1;
            q.push({nx,ny});
          }
        }
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}