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

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

思路:象形文字有一些特点,分别有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 ;
}
05-11 20:29