UVa 1103 - Ancient Messages(DFS:Floodfill)

给出六种象形文字。然后给出十六进制的数表,求对应数表的01图所含有的字母,获得字母按字典序打印。

书上给了很巧妙的思路:每个字母中白色块的数目不同,依此判断字母是什么。

先把数表转化为二进制。然后进行一次Floodfill把所有的象形文字独立出来。要注意先加一圈“空气”使得无关的0连通。

然后对每个独立的象形文字进行Floodfill,求有几个白色连通块。查找出对应的字母。该字母数量+1。

最后按字典序输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int maxn=210;
const int a[6]={1,5,3,2,4,0};//打表储存字母和字典序的顺序。
const char b[7]="WAKJSD";
int h,w,cnt[6],ct;
bool vis[maxn][maxn],g[maxn][maxn];
map<char,int> hex;
void pre(){//预处理十六进制转化数组。
for(int i=0;i<10;++i) hex['0'+i]=i;
for(int i=0;i<6;++i) hex['a'+i]=10+i;
return;
}
bool read(){
scanf("%d%d",&h,&w);
if(!h&&!w) return false;
memset(g,0,sizeof(g));
for(int i=1;i<=h;++i){
getchar();
int pos=1;
for(int j=1;j<=w;++j){
int c=hex[getchar()];//读入的同时进行处理。
for(int k=3;k>=0;--k)
g[i][pos++]=c&(1<<k);
}
}
w*=4;
return true;
}
bool in(int x,int y){
return x>=0&&x<=h+1&&y>=0&&y<=w+1;
}
void dfs(int x,int y,bool k){//Floodfill。
if(!in(x,y)||vis[x][y]) return;
if(!k&&g[x][y]) return;
if(k&&!g[x][y]){
++ct;
dfs(x,y,0);
return;
}
vis[x][y]=true;
dfs(x,y+1,k);
dfs(x+1,y,k);
dfs(x,y-1,k);
dfs(x-1,y,k);
return;
}
void solve(){
memset(cnt,0,sizeof(cnt));
memset(vis,0,sizeof(vis));
dfs(0,0,0);
for(int i=0;i<=h;++i){
for(int j=0;j<=w;++j){
if(g[i][j]&&!vis[i][j]){
ct=0;
dfs(i,j,1);
++cnt[ct];
}
}
}
for(int i=0;i<6;i++)
while(cnt[a[i]]--) putchar(b[a[i]]);
printf("\n");
return;
}
int main(){
pre();
int t=0;
while(read()){
printf("Case %d: ",++t);
solve();
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。