学步园

练习floodfill很好的题。第一次考虑从内部有模块的点开始floodfill，发现无法识别内部空仓和外部空仓。反向思考，从外部空仓进入模块，得解。

#include <cstdio><br /> #include <string></p> <p>int b[60][60][60];<br /> bool used[216000];<br /> int q[216000];<br /> int N, M, K, L;<br /> int dir[6][3] =<br /> {<br /> { 1, 0, 0 }, { -1, 0, 0 }, { 0, 1, 0 }, { 0, -1, 0 }, { 0, 0, 1 }, { 0, 0, -1 }<br /> };</p> <p>int getx ( int n, int m, int k )<br /> {<br /> return ( k * M + m ) * N + n;<br /> }</p> <p>void setx ( int x, int &n, int &m, int &k )<br /> {<br /> k = x / ( N * M );<br /> x = x % ( N * M );<br /> m = x / N;<br /> n = x % N;<br /> }</p> <p>int main ()<br /> {<br /> //freopen ( "in.txt", "r", stdin );<br /> while ( scanf ( "%d%d%d%d", &N, &M, &K, &L ) && N )<br /> {<br /> memset ( b, 0, sizeof ( b ) );<br /> int i, x, n, m, k;<br /> for ( i = 0; i < L; i ++ )<br /> {<br /> scanf ( "%d", &x );<br /> setx ( x, n, m, k );<br /> b[n][m][k] = 1;<br /> }<br /> memset ( used, 0, sizeof ( used ) );<br /> int op, ed;<br /> // 对外层平面的所有0值点进行floodfill，进入1值点的即计数<br /> int count = 0;<br /> for ( n = 0; n < N; n ++ )<br /> {<br /> for ( m = 0; m < M; m ++ )<br /> {<br /> for ( k = 0; k < K; k ++ )<br /> {<br /> if ( n != 0 && n != N - 1 && m != 0 && m != M - 1 && k != 0 && k != K - 1 )<br /> continue;<br /> if ( b[n][m][k] == 0 )<br /> {<br /> b[n][m][k] = 2;<br /> int x = getx ( n, m, k );<br /> q[0] = x;<br /> for ( op = -1, ed = 0; op ++ < ed; )<br /> {<br /> int xx = q[op];<br /> int kk, mm, nn;<br /> setx ( xx, nn, mm, kk );<br /> int l;<br /> for ( l = 0; l < 6; l ++ )<br /> {<br /> int nnn = nn + dir[l][0], mmm = mm + dir[l][1], kkk = kk + dir[l][2];<br /> if ( nnn < 0 || nnn >= N || mmm < 0 || mmm >= M || kkk < 0 || kkk >= K )<br /> continue;<br /> if ( b[nnn][mmm][kkk] == 1 )<br /> count ++;<br /> if ( b[nnn][mmm][kkk] == 0 )<br /> {<br /> b[nnn][mmm][kkk] = 2;<br /> int xxx = getx ( nnn, mmm, kkk );<br /> q[++ ed] = xxx;<br /> }<br /> }<br /> }<br /> }<br /> }<br /> }<br /> }<br /> for ( n = 0; n < N; n ++ )<br /> {<br /> for ( m = 0; m < M; m ++ )<br /> {<br /> if ( b[n][m][0] == 1 )<br /> count ++;<br /> if ( b[n][m][K - 1] == 1 )<br /> count ++;<br /> }<br /> }<br /> for ( k = 0; k < K; k ++ )<br /> {<br /> for ( m = 0; m < M; m ++ )<br /> {<br /> if ( b[0][m][k] == 1 )<br /> count ++;<br /> if ( b[N - 1][m][k] == 1 )<br /> count ++;<br /> }<br /> }<br /> for ( n = 0; n < N; n ++ )<br /> {<br /> for ( k = 0; k < K; k ++ )<br /> {<br /> if ( b[n][0][k] == 1 )<br /> count ++;<br /> if ( b[n][M - 1][k] == 1 )<br /> count ++;<br /> }<br /> }</p> <p> printf ( "The number of faces needing shielding is %d./n", count );<br /> }<br /> return 0;<br /> }