# include <stdio.h>
# include <stdbool.h>
bool data[21][21][21];
bool used[21][21][21];
bool face1[9][21][21],face2[9][21][21],face3[9][21][21];
int n;
void test()
{
  int i,j,k;
  printf("face1\n");
  for(k=1;k<=8;k++)
  {
   printf("num=%d\n",k);
   for(i=1;i<=n;i++)
   {
    for(j=1;j<=n;j++) 
      if(face1[k][i][j]) printf("●");
      else printf("  "); 
    printf("\n");
   }
   printf("\n");
  }
  printf("face2\n");
  for(k=1;k<=8;k++)
  {
   printf("num=%d\n",k);
   for(i=1;i<=n;i++)
   {
    for(j=1;j<=n;j++) 
      if(face2[k][i][j]) printf("●");
      else printf("  "); 
    printf("\n");
   }
   printf("\n");
  }
  printf("face3\n");
  for(k=1;k<=8;k++)
  {
   printf("num=%d\n",k);
   for(i=1;i<=n;i++)
   {
    for(j=1;j<=n;j++) 
      if(face3[k][i][j]) printf("●");
      else printf("  "); 
    printf("\n");
   }
   printf("\n");
  }
}
void dfs(int x,int y,int z)
{
     if(x<1||x>n||y<1||y>n||z<1||z>n) return;
     else if(used[x][y][z]) return;
     else if(!data[x][y][z]) return;
     else
     {
       used[x][y][z]=1;
       dfs(x+1,y,z);
       dfs(x-1,y,z);
       dfs(x,y+1,z);
       dfs(x,y-1,z);
       dfs(x,y,z+1);
       dfs(x,y,z-1);
     }
}
void makeface()
{
   int i,j,k;
   for(k=2;k<=4;k++)
     for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
      {
       face1[k][j][n-i+1]=face1[k-1][i][j];
       face2[k][j][n-i+1]=face2[k-1][i][j];
       face3[k][j][n-i+1]=face3[k-1][i][j];
      }
   for(k=1;k<=4;k++)
      for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
          face1[k+4][n-i+1][j]=face1[k][i][j];
          face2[k+4][n-i+1][j]=face2[k][i][j];
          face3[k+4][n-i+1][j]=face3[k][i][j];
        }
}
void makeblock(int c1,int c2,int c3)
{
     int i,j,k;
     for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(!face1[c1][i][j])
          for(k=1;k<=n;k++)
            data[i][j][k]=0;  
     for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(!face2[c2][i][j])
          for(k=1;k<=n;k++)
            data[k][i][j]=0;
     for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(!face3[c3][i][j])
          for(k=1;k<=n;k++)
            data[i][k][j]=0;            
}
bool chkthrouth(int c1,int c2,int c3)
{
     int i,j,k;
     for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(face1[c1][i][j])
        {
          bool flag=0;
          for(k=1;k<=n;k++)
            if(data[i][j][k]) {flag=1;break;}
          if(!flag) return 0;
        }  
     for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(face2[c2][i][j])
        {
         bool flag=0;
          for(k=1;k<=n;k++)
            if(data[k][i][j]) {flag=1;break;}
          if(!flag) return 0;
         }
     for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(face3[c3][i][j])
        {
          bool flag=0;
          for(k=1;k<=n;k++)
            if(data[i][k][j]) {flag=1;break;}
          if(!flag) return 0;
        }  
        return 1;          
}
bool sub_jud()
{
     int x,y,z;
     memset(used,0,sizeof(used));
     for(x=1;x<=n;x++)
       for(y=1;y<=n;y++)
       {
          if(!used[x][y][1]&&data[x][y][1])
             {dfs(x,y,1);goto here;}
       }  
     here:;
     for(x=1;x<=n;x++) 
       for(y=1;y<=n;y++)
         for(z=1;z<=n;z++)
           if(!used[x][y][z]&&data[x][y][z]) return 0;
     return 1;
}
bool jud()
{
    makeface(); 

    int i,j,k;
    for(i=1;i<=8;i++)
      for(j=1;j<=8;j++)
        for(k=1;k<=8;k++)
        {
         memset(data,1,sizeof(data));
         makeblock(i,j,k);
         if(chkthrouth(i,j,k)&&sub_jud()) return 1;
        }
   return 0;
}
int main()
{
    int count=0;
    while(1)
    {
        scanf("%d",&n);
        if(!n) break;
        int i,j;
        for(i=1;i<=n;i++)
        {
         getchar();
         for(j=1;j<=n;j++)
         {
          char temp;
          scanf("%c",&temp);
          if(temp=='X') face1[1][j][i]=1;
          else face1[1][j][i]=0;
         }
        }
        for(i=1;i<=n;i++)
        {
         getchar();
         for(j=1;j<=n;j++)
         {
          char temp;
          scanf("%c",&temp);
          if(temp=='X') face2[1][j][i]=1;
          else face2[1][j][i]=0;
         }
        }
        for(i=1;i<=n;i++)
        {
         getchar();
         for(j=1;j<=n;j++)
         {
          char temp;
          scanf("%c",&temp);
          if(temp=='X') face3[1][j][i]=1;
          else face3[1][j][i]=0;
         }
        }
        if(jud()) printf("Data set %d: Valid set of patterns\n",++count);
        else printf("Data set %d: Impossible combination\n",++count);
    }
    return 0;
}
        
         
        
    

• Re:test函数是我用来测试的。。。一个小错误查了我半天（真正意义上的半天） (5226) yzhw 2009-05-01 22:04:30
• 或者说：是否连通，是否满足三视图 (5226) yc5_yc 2012-08-05 13:48:47