1096.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"memory.h"
char map[60][60][60];


long answer;

int n,m,h;

void find()
{int i,j,k,key;
answer=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{key=1;
 for(k=0;k<h;k++)if(map[k][i][j]==1&&key){answer++;key=0;}
 		else if(map[k][i][j]==2)key=1;
 key=1;
 for(k=h-1;k>=0;k--)if(map[k][i][j]==1&&key){answer++;key=0;}
                else if(map[k][i][j]==2)key=1;
		 
}

for(i=0;i<h;i++)
for(j=0;j<m;j++)
{key=1;
	
for(k=0;k<n;k++)if(map[i][j][k]==1&&key){answer++;key=0;}
		else if(map[i][j][k]==2)key=1;
key=1;		
for(k=n-1;k>=0;k--)if(map[i][j][k]==1&&key){answer++;key=0;}
                else if(map[i][j][k]==2)key=1;
		
}


for(i=0;i<h;i++)
for(j=0;j<n;j++)
{
key=1;	
 for(k=0;k<m;k++)if(map[i][k][j]==1&&key){answer++;key=0;}
 		else if(map[i][k][j]==2)key=1;
key=1;
 for(k=m-1;k>=0;k--)if(map[i][k][j]==1&&key){answer++;key=0;}
                 else if(map[i][k][j]==2)key=1;
	
}

}  

void color(int a,int b,int c)
{map[a][b][c]=2;
if(a>0&&map[a-1][b][c]==0)color(a-1,b,c);
if(a<h-1&&map[a+1][b][c]==0)color(a+1,b,c);

if(b>0&&map[a][b-1][c]==0)color(a,b-1,c);
if(b<m-1&&map[a][b+1][c]==0)color(a,b+1,c);

if(c>0&&map[a][b][c-1]==0)color(a,b,c-1);
if(c<n-1&&map[a][b][c+1]==0)color(a,b,c+1);
}



void findface()
{int i,j,k;
for(i=0,j=0;j<m;j++)
for(k=0;k<n;k++)
if(map[i][j][k]==0)color(i,j,k);

for(i=h-1,j=0;j<m;j++)
for(k=0;k<n;k++)
if(map[i][j][k]==0)color(i,j,k);

for(j=0,i=0;i<h;i++)
for(k=0;k<n;k++)
if(map[i][j][k]==0)color(i,j,k);

for(j=m-1,i=0;i<h;i++)
for(k=0;k<n;k++)
if(map[i][j][k]==0)color(i,j,k);

for(k=0,i=0;i<h;i++)
for(j=0;j<m;j++)
if(map[i][j][k]==0)color(i,j,k);

for(k=n-1,i=0;i<h;i++)
for(j=0;j<m;j++)
if(map[i][j][k]==0)color(i,j,k);
}

int main()
{int l,i,s;
	while(1)
	{cin>>n>>m>>h>>l;
		if(n==0&&m==0&&h==0&&l==0)break;
		memset(map,0,60*60*60*sizeof(char));
		for(i=0;i<l;i++)
		{cin>>s;
			map[s/(n*m)][s%(n*m)/n][s%n]=1;
		}
	findface();
	find();
	cout<<"The number of faces needing shielding is "<<answer<<"."<<endl;
	}
return 0;
}