naoya_t@topcoder

SRM211 Div1 Medium: grafixMask

過去問, 練習, Tutorials | 00:28 |

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

• 問題がなかなか頭に入らなかった
• ニコ動をBGMにしながらは無理か
• いつもpriority_queue使うけど今日は普通のqueueで。合理的に使い分けているわけではない
• 214.27points (50'0''), passed system test

#define RC 240000
class grafixMask {
 public:
  vector<int> sortedAreas(vector<string> rectangles) {
    vector<int> wh(RC,0); // r*600+c
    int rem=RC;
    tr(rectangles,it){
      vector<int> rs = map_atoi(split(*it));
      for(int r=rs[0]; r<=rs[2]; r++){
        for(int c=rs[1]; c<=rs[3]; c++){
          int rc=r*600 + c;
          if(wh[rc]==0){ wh[rc]=-1; rem--; }
        }
      }
    }

    vector<int> ans;
    int room=1;
    while(rem){
      // find emptypoint
      int erc=-1;
      rep(rc,RC) if (wh[rc]==0){ erc=rc; goto found; }
      if (erc==-1) goto err;
   found:
      // flood fill
      queue<int> q;
      vector<bool> vac(RC,false);
      rep(rc,RC) if(wh[rc]==0) vac[rc]=true;
      q.push(erc); vac[erc]=false;
      while(!q.empty()){
        int rc=q.front(); q.pop();
        if(wh[rc]==0){ wh[rc]=room; rem--; }
        int r=rc/600, c=rc%600;
        if(1<=r && vac[rc-600]){ q.push(rc-600); vac[rc-600]=false;}
        if(r<=398 && vac[rc+600]){ q.push(rc+600); vac[rc+600]=false;}
        if(1<=c && vac[rc-1]){ q.push(rc-1); vac[rc-1]=false;}
        if(c<=598 && vac[rc+1]){ q.push(rc+1); vac[rc+1]=false;}
      }
      room++;
    }
    ans.resize(room-1); rep(i,room-1) ans[i]=0;
    rep(rc,RC){
      if (wh[rc]>0) ans[wh[rc]-1]++;
    }
    sort(all(ans));
 err:
    return ans;
  }
};