PKU 2882 Food Cubes
http://poj.org/problem?id=2882
立方体によって空間が何個に分割されているかを数えるというような問題。
いろいろ迷走した挙句にbfs書いてギリギリでACもらいました。
int dx[]={0,1,0,-1,0,0},dy[]={1,0,-1,0,0,0}; int dz[]={0,0,0,0,1,-1}; int n; bool app[110][110][110]; void bfs(int x,int y,int z){ queue<pair<int,PI> > q; q.push(mp(x,mp(y,z))); app[x][y][z]=true; while(!q.empty()){ x=q.front().F; y=q.front().S.F; z=q.front().S.S; q.pop(); rep(i,6){ int nx=x+dx[i],ny=y+dy[i],nz=z+dz[i]; if(nx<0 || ny<0 || nz<0 || nx>100 || ny>100 || nz>100 || app[nx][ny][nz])continue; app[nx][ny][nz]=true; q.push(mp(nx,mp(ny,nz))); } } } void solve(){ cin>>n; memset(app,0,sizeof(app)); rep(i,n){ int x,y,z; cin>>x>>y>>z; app[x][y][z]=1; } int ans=-1; rep(i,101)rep(j,101)rep(k,101){ if(app[i][j][k])continue; ++ans; bfs(i,j,k); } cout<<ans<<endl; } main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--) solve(); }