UVa 1103 - Ancient Messages（DFS：Floodfill）

发表于 分类于 ， Disqus：

给出六种象形文字。然后给出十六进制的数表，求对应数表的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博客，格式可能有所偏差。 **

相关文章