PKU 3338 Rectangle Cutting
http://poj.org/problem?id=3338
h*wのケーキを長方形型に何回か切り分けたときにいくつにわかれるかを求めろというような問題。
実装ゲー。
一瞬ものすごく面倒くさいんじゃないかと思ったけれど、そうでもなく感じました。
長方形の切り分けの入力が若干意地が悪い。
int cake[20][20]; bool vis[20][20]; main(){ int h,w; while(cin>>h>>w,h|w){ memset(cake,0,sizeof(cake)); int n; cin>>n; int p=0; rep(i,n){ int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); memset(vis,0,sizeof(vis)); for(int x=x1;x<x2;++x){ for(int y=y1;y<y2;++y){ if(vis[x][y])continue; ++p; int ba=cake[x][y]; for(int tx=x1;tx<x2;++tx){ for(int ty=y1;ty<y2;++ty){ if(cake[tx][ty]==ba){ cake[tx][ty]=p; vis[tx][ty]=true; } } } } } } int ans=0; memset(vis,0,sizeof(vis)); rep(i,w){ rep(j,h){ if(vis[i][j])continue; queue<PI>q; ++ans; q.push(mp(i,j)); while(!q.empty()){ int cx=q.front().F,cy=q.front().S; q.pop(); if(vis[cx][cy])continue; vis[cx][cy]=true; rep(k,4){ int nx=cx+dx[k],ny=cy+dy[k]; if(nx<0 || w<=nx || ny<0 || h<=ny || vis[nx][ny] || cake[i][j]!=cake[nx][ny])continue; q.push(mp(nx,ny)); } } } } cout<<ans<<endl; } }