寝癖頭の解法

勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #sheet - 色紙 (Sheet)

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

#sheet - 色紙 (Sheet)

https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf

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

/*
AtCoder Problems in C++
#sheet - 色紙 (Sheet)
https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
  ll n;
  cin>>n;
  ll h,w;
  cin>>w>>h;
  vector<vector<ll>> c(h,vector<ll>(w));
  for(ll i=0;i<h;i++){
    for(ll j=0;j<w;j++){
      cin>>c[i][j];
      c[i][j]--;
    }
  }
  vector<vector<ll>> g(n);
  for(ll i=0;i<n;i++){
    ll minh=h,minw=w,maxh=0,maxw=0;
    for(ll j=0;j<h;j++){
      for(ll k=0;k<w;k++){
        if(c[j][k]==i){
          minh=min(minh,j);
          minw=min(minw,k);
          maxh=max(maxh,j);
          maxw=max(maxw,k);
        }
      }
    }
    for(ll j=minh;j<=maxh;j++){
      for(ll k=minw;k<=maxw;k++){
        if(c[j][k]==-1 || c[j][k]==i){
          continue;
        }
        ll t=c[j][k];
        g[i].push_back(t);
      }
    }
  }
  vector<ll> ans;
  vector<ll> v(n);
  for(ll i=0;i<n;i++){
    for(auto j : g[i]){
      v[j]++;
    }
  }
  queue<ll> q;
  for(ll i=0;i<n;i++){
    if(v[i]==0){
      q.push(i);
    }
  }
  while(!(q.empty())){
    ll num=q.front();
    q.pop();
    ans.push_back(num);
    for(auto i : g[num]){
      v[i]--;
      if(v[i]==0){
        q.push(i);
      }
    }
  }
  for(ll i=0;i<n;i++){
    cout<<ans[i]+1<<((i==n-1) ? "\n" : " ");
  }
  return 0;
}