1114 Food Cubes 3D BFS

//3D水广搜 搜有几个被立方体围起来的空白部分 //直接搜空白部分 遇到边界表示空白部分不是hole就可以了 //在机子上跑样例10s，那个汗呀，硬头皮交上去。。0.33s //我汗，我机子破了 #include <iostream> #include <queue> #include <cstdio> #include <cstring> using namespace std; bool visited[101][101][101]; int t, n, x, y, z, result; bool addadd; int chx[] = { 0,0,1,-1,0,0 }, chy[] = { 1,-1,0,0,0,0 }, chz[] = { 0,0,0,0,1,-1 }; struct Triple { int x,y,z; Triple( int a,int b, int c ) :x(a), y(b), z(c) { } }; int main() { //freopen("1.txt","r",stdin); scanf("%d",&t); while( t-- ) { result = 0; memset( visited,false,sizeof(visited) ); scanf("%d",&n); while( n-- ) { scanf("%d%d%d",&x,&y,&z ); visited[x][y][z] = true; } queue< Triple > q; for( int i = 2;i < 100;i++ ) { for( int j = 2;j < 100;j++ ) { for( int k = 2;k < 100;k++ ) { if( !visited[i][j][k] ) { addadd = true; q.push( Triple(i,j,k) ); while( !q.empty() ) { Triple top = q.front(); q.pop(); int x1 = top.x, y1 = top.y, z1 = top.z; for( int i2 = 0;i2 < 6;i2++ ) { int x2 = x1 + chx[i2], y2 = y1 + chy[i2], z2 = z1 + chz[i2]; if( visited[x2][y2][z2] ) continue; else { if( x2 == 1 || x2 == 100 || y2 == 1 || y2 == 100 || z2 == 1 || z2 == 100 ) { addadd = false; } else { visited[x2][y2][z2] = true; q.push( Triple(x2,y2,z2) ); } } } } if( addadd ) result ++; } } } } printf("%d/n",result ); } }