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":" "); }