Codeforces 31 D. Chocolate

問題

WxHのチョコレートがある。これをn本の線分にしたがって切断する。
n本の直線は、両端点(x1,y1),(x2,y2)によって与えられる。

切断後のそれぞれのチョコレートの片の面積を求めよ。

制約条件

W,H≦100
線分は座標軸に平行かつx1,y1,x2,y2は全て整数

方針

チョコレートをWxHマスのグリッドとみて、深さ優先探索でつながっている部分の面積を見るだけ。
制約も小さいので特に工夫は必要ない。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int w,h,n;
bool tate[101][101],yoko[101][101];
bool v[101][101];

int dfs(int y,int x){
  v[y][x]=1;
  int res=1;
  rep(d,4){
    int ny=y+dy[d],nx=x+dx[d];
    if(ny<0||nx<0||ny>=h||nx>=w||v[ny][nx])continue;
    if(d==0&&yoko[y][x]||d==2&&yoko[y+1][x])continue;
    if(d==1&&tate[y][x]||d==3&&tate[y][x+1])continue;
    res+=dfs(ny,nx);
  }
  return res;
}
void run(){
  cin>>w>>h>>n;
  rep(i,n){
    int x,y,X,Y;
    cin>>x>>y>>X>>Y;
    if(x==X)for(int j=y;j<Y;j++)tate[j][x]=1;
    else for(int j=x;j<X;j++)yoko[y][j]=1;
  }
  vi ans;
  rep(i,h)rep(j,w)if(!v[i][j])ans.pb(dfs(i,j));
  sort(all(ans));
  rep(i,n+1)cout<<ans[i]<<(i==n?"\n":" ");
}