题目大意：给出一幅画，找出里面的象形文字。
要你翻译这幅画，把象形文字按字典序输出。
思路：象形文字有一些特点，分别有0个圈、1个圈、2个圈...5个圈。然后dfs或者bfs，就像油井问题一样，找出在同一块的0，找出在同一块的1，分别标上记号。
对于每个同一块的1，如果它们只和1个‘0’的块相邻，就表明这个象形文字没有圈。如果和2个‘1’的块相邻，就说明这个象形文字有一个圈。依此类推...和6个‘1’块相邻的就有五个圈。
最后统计一下每个象形文字和多少不同的块相邻，排一个序，输出。 要注意的是，处理输入的时候，给读入的图的周围留一个‘0’构成的圈。为什么呢？这个自己想。
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <map> 7 using namespace std; 8 int H,W; 9 char Map[220][440]; 10 int vis[220][440]; 11 int chr[220][440]; 12 int wblc_cnt,bblc_cnt; 13 char hie[6]={'W','A','K','J','S','D'}; 14 int dx[4]={0,0,1,-1}; 15 int dy[4]={1,-1,0,0}; 16 map<int,bool> Hsh[80010]; 17 int bccnt[80010]; 18 char ans[80010]; 19 int comp(const void *_a,const void *_b) 20 { 21 char a=*(char *)_a; 22 char b=*(char *)_b; 23 return a-b; 24 } 25 26 void dfs1(int x,int y) 27 { 28 vis[x][y]=wblc_cnt; 29 int nx,ny; 30 for(int i=0;i<4;i++){ 31 nx=dx[i]+x; 32 ny=dy[i]+y; 33 if(nx>=0&&nx<H&&ny>=0&&ny<W && !vis[nx][ny] && Map[nx][ny]=='0')dfs1(nx,ny); 34 } 35 } 36 void dfs2(int x,int y) 37 { 38 chr[x][y]=bblc_cnt; 39 int nx,ny; 40 for(int i=0;i<4;i++){ 41 nx=dx[i]+x; 42 ny=dy[i]+y; 43 if(nx>=0&&nx<H&&ny>=0&&ny<W&&!chr[nx][ny]){ 44 if(Map[nx][ny]=='0'){ 45 if(Hsh[bblc_cnt].find(vis[nx][ny]) != Hsh[bblc_cnt].end())continue; 46 Hsh[bblc_cnt].insert(pair<int,bool>(vis[nx][ny],true)); 47 }else dfs2(nx,ny); 48 } 49 } 50 } 51 int main() 52 { 53 char str[60]; 54 int kase=1; 55 while(~scanf("%d%d",&H,&W)&&(H+W)){ 56 printf("Case %d: ",kase++); 57 getchar(); 58 memset(Map,0,sizeof(Map)); 59 memset(vis,0,sizeof(vis)); 60 memset(chr,0,sizeof(chr)); 61 for(int i=0;i<=4*W+8;i++)Map[0][i]=Map[H+1][i]='0'; 62 for(int i=1;i<=H;i++){ 63 gets(str); 64 for(int j=0;j<4;j++) 65 Map[i][j]=Map[i][4+W*4+j]='0'; 66 for(int j=0;j<W;j++){ 67 int x; 68 if('0'<=str[j] && str[j]<='9') 69 x=str[j]-'0'; 70 else 71 x=10+str[j]-'a'; 72 for(int k=0;k<4;k++){ 73 if(x & 1<<(3-k)) Map[i][4+j*4+k]='1'; 74 else Map[i][4+j*4+k]='0'; 75 } 76 } 77 } 78 W+=2;W*=4; 79 H+=2; 80 wblc_cnt=0; 81 for(int i=0;i<H;i++)for(int j=0;j<W;j++) 82 if(vis[i][j]==0 && Map[i][j]=='0'){ 83 wblc_cnt++; 84 dfs1(i,j); 85 } 86 bblc_cnt=0; 87 for(int i=0;i<H*W;i++) Hsh[i].clear(); 88 for(int i=0;i<H;i++)for(int j=0;j<W;j++) 89 if(chr[i][j]==0 && Map[i][j]=='1'){ 90 bblc_cnt++; 91 dfs2(i,j); 92 } 93 for(int i=1;i<=bblc_cnt;i++) 94 bccnt[i]=Hsh[i].size(); 95 for(int i=1;i<=bblc_cnt;i++) 96 ans[i]=hie[bccnt[i]-1]; 97 qsort(ans+1,bblc_cnt,sizeof(char),comp); 98 ans[bblc_cnt+1]=' '; 99 puts(ans+1); 100 } 101 return 0; 102 }