uva1103

进制转换+DFS（连通块）

链接：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=258&page=show_problem&problem=3544

先分离成一个一个的块，之后在每个块里找空白，走过的块就标记成-1；

ans存答案，str是对应字典序输出，change 进制转换数组；

在变量中找不变量，每个图形里的空白块数量都不同；

两个dfs，一个标记空白快，一个标记走过的块；

代码：

#include <iostream>
#include <cstring>
#define mes(a) memset(a,0,sizeof(a))
using namespace std;

int a[210][210];
int ans[8];//存有几个相同的图按字典序输出 
char str[]={'A','D','J','K','S','W'};//字典序 
int change[][4]={
               {0,0,0,0},
               {0,0,0,1},
               {0,0,1,0},
               {0,0,1,1},
               {0,1,0,0},
               {0,1,0,1},
               {0,1,1,0},
               {0,1,1,1},
               {1,0,0,0},
               {1,0,0,1},
               {1,0,1,0},
               {1,0,1,1},
               {1,1,0,0},
               {1,1,0,1},
               {1,1,1,0},
               {1,1,1,1}};
int n,m,count;

bool check(int x,int y)
{
    if((x>=0&&x<=n+1)&&(y>=0&&y<=m+1))
     return true;
    return false;
}

void dfs(int x,int y)//分块 ,外围为0的直接标记成-1 
{
   if(!check(x,y)||a[x][y])//找每个分块的边界 
    return ;
    a[x][y]=-1;
    dfs(x+1,y);
    dfs(x,y+1);
    dfs(x-1,y);
    dfs(x,y-1);
 }
 
void DFS(int x,int y)//走过的全变成-1 
{
    if(!check(x,y)||a[x][y]==-1)//出口 
      return ;
    if(a[x][y]==0)//找中间的空白 
    {
        count++;
        dfs(x,y);//相邻的全变成-1 
        return ;
    }
    a[x][y]=-1;
    DFS(x+1,y);
    DFS(x-1,y);
    DFS(x,y+1);
    DFS(x,y-1);
   }       
int main()
{
    int t=1;
    char ch;
    while(cin>>n>>m&&n&&m)
    {
    int i,j;
    mes(ans);
    mes(a);
    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            cin>>ch;
            //getchar();
            if(ch>='0' && ch<='9')
            {
                int l=0;
                for(int k=j*4+1; k<=j*4+4; k++)
                  a[i+1][k]=change[ch-'0'][l++];
            }
            else if(ch>='a' && ch<='f')
            {
                int l=0;
                for(int k=j*4+1; k<=j*4+4; k++)
                  a[i+1][k]=change[ch-'a'+10][l++];
            }
         }
    }
    
    m*=4;
    /*for(int i=0; i<=n+1; i++)
     {
     for(int j=0; j<=m+1; j++)
      printf("%d",a[i][j]);
      cout<<"
";
     }*/
     dfs(0,0);
     /*for(int i=0; i<=n+1; i++)
     {
     for(int j=0; j<=m+1; j++)
      printf("%2d",a[i][j]);
      cout<<"
";
     }*/
     
     cout<<"Case "<<t++<<": ";
     for(int i=1; i<=n; i++)
     {
         for(int j=1; j<=m; j++)
         {
             if(a[i][j]==1)
             {
                 count=0;
                 DFS(i,j);
                 /*for(int i=0; i<=n+1; i++)
                {
                for(int j=0; j<=m+1; j++)
                 printf("%2d",a[i][j]);
                 cout<<"
";
                }*/
                 if(count==0)
                   ans[5]++;
                 if(count==1)
                   ans[0]++;
                 if(count==2)
                   ans[3]++;
                 if(count==3)
                   ans[2]++;
                 if(count==4)
                   ans[4]++;
                 if(count==5)
                   ans[1]++;
             }
         }
     }
     for(int i=0; i<6; i++)
     {
         while(ans[i]--)
          cout<<str[i];    
     }
     cout<<endl;
}
    return 0;
}
/*
5 15
fff00fff000f0f0
f0f00f0f000f0f0
fff0fffff0fffff
f0f000f00000f00
fff000f00000f00 
AKW
 */