hdu 3839 Ancient Messages （dfs ）

题目大意：给出一幅画，找出里面的象形文字。

要你翻译这幅画，把象形文字按字典序输出。

思路：象形文字有一些特点，分别有0个圈、1个圈、2个圈...5个圈。然后dfs或者bfs，就像油井问题一样，找出在同一块的0，找出在同一块的1，分别标上记号。

对于每个同一块的1，如果它们只和1个‘0’的块相邻，就表明这个象形文字没有圈。如果和2个‘1’的块相邻，就说明这个象形文字有一个圈。依此类推...和6个‘1’块相邻的就有五个圈。

最后统计一下每个象形文字和多少不同的块相邻，排一个序，输出。 要注意的是，处理输入的时候，给读入的图的周围留一个‘0’构成的圈。为什么呢？这个自己想。

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <cstdlib>

 #include <vector>

 #include <map>

 using namespace std;

 int H,W;

 char Map[][];

 int vis[][];

 int chr[][];

 int wblc_cnt,bblc_cnt;

 char hie[]={'W','A','K','J','S','D'};

 int dx[]={,,,-};

 int dy[]={,-,,};

 map<int,bool> Hsh[];

 int bccnt[];

 char ans[];

 int comp(const void *_a,const void *_b)

 {

     char a=*(char *)_a;

     char b=*(char *)_b;

     return a-b;

 }

 void dfs1(int x,int y)

 {

     vis[x][y]=wblc_cnt;

     int nx,ny;

     for(int i=;i<;i++){

         nx=dx[i]+x;

         ny=dy[i]+y;

         if(nx>=&&nx<H&&ny>=&&ny<W && !vis[nx][ny]  && Map[nx][ny]=='')dfs1(nx,ny);

     }

 }

 void dfs2(int x,int y)

 {

     chr[x][y]=bblc_cnt;

     int nx,ny;

     for(int i=;i<;i++){

         nx=dx[i]+x;

         ny=dy[i]+y;

         if(nx>=&&nx<H&&ny>=&&ny<W&&!chr[nx][ny]){

             if(Map[nx][ny]==''){

                 if(Hsh[bblc_cnt].find(vis[nx][ny]) != Hsh[bblc_cnt].end())continue;

                 Hsh[bblc_cnt].insert(pair<int,bool>(vis[nx][ny],true));

             }else dfs2(nx,ny);

         }

     }

 }

 int main()

 {

     char str[];

     int kase=;

     while(~scanf("%d%d",&H,&W)&&(H+W)){

         printf("Case %d: ",kase++);

         getchar();

         memset(Map,,sizeof(Map));

         memset(vis,,sizeof(vis));

         memset(chr,,sizeof(chr));

         for(int i=;i<=*W+;i++)Map[][i]=Map[H+][i]='';

         for(int i=;i<=H;i++){

             gets(str);

             for(int j=;j<;j++)

                 Map[i][j]=Map[i][+W*+j]='';

             for(int j=;j<W;j++){

                 int x;

                 if(''<=str[j] && str[j]<='')

                     x=str[j]-'';

                 else

                     x=+str[j]-'a';

                 for(int k=;k<;k++){

                     if(x & <<(-k)) Map[i][+j*+k]='';

                     else Map[i][+j*+k]='';

                 }

             }

         }

         W+=;W*=;

         H+=;

         wblc_cnt=;

         for(int i=;i<H;i++)for(int j=;j<W;j++)

             if(vis[i][j]== && Map[i][j]==''){

                 wblc_cnt++;

                 dfs1(i,j);

             }

         bblc_cnt=;

         for(int i=;i<H*W;i++) Hsh[i].clear();

         for(int i=;i<H;i++)for(int j=;j<W;j++)

             if(chr[i][j]== && Map[i][j]==''){

                 bblc_cnt++;

                 dfs2(i,j);

             }

         for(int i=;i<=bblc_cnt;i++)

             bccnt[i]=Hsh[i].size();

         for(int i=;i<=bblc_cnt;i++)

             ans[i]=hie[bccnt[i]-];

         qsort(ans+,bblc_cnt,sizeof(char),comp);

         ans[bblc_cnt+]='\0';

         puts(ans+);

     }

     return ;

 }