UVA 1103

Posted on | In , | Visitors:

This is my blog.
最近不下雨了
可是还是很冷呢
龟速学习中
今天的练习不知道写点什么
看到一道关于欧拉函数的题
复习了一下它的性质
补充了一下blog
doc老师的题不会做
就刷起了vijos
自从放下dp后都没有打卡过此oj
至于今天的内容
就写一下UVA 1103吧！

题意

给你由黑白方块组成的象形文字，让你输出这象形文字是什么。其中，象形文字是题目中给出的六个中的，但是个数和摆放位置不限定，也就是不一定对齐。再者，这些文字不会交叉叠放。构成的方块由0，1表示，其中1表示黑色。而这些二进制又被合成为了十六进制给你。按字典序输出象形文字。

题解

刚开始在书上看到简版题意，有点云里雾里，不过倒是给我看英文题意时，有了帮助。同时得到了提示，观察这六个文字的不同。（这也算是技巧吧，将文字简化）
在题意中，我已大概将要做的事情罗列了一下：
1.我们拿到的是十六进制，所以需要十六进制转二进制
2.求连通块，dfs，并给上标记
3.对其中黑色的连通块，寻找其附近除了背景白色以外，白色连通块的个数
4.根据白色的个数，得出此黑色连通块所描述的文字
5.将这些文字排序，输出

AC代码

多次编译错误，发现我少些了两个头文件？？！
Xcode居然不提醒我了，不开心。

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int maxh=200+5;
const int maxw=50*4+5;
const char* s="WAKJSD";//根据几个洞
const int dirx[4]={0,0,-1,1};
const int diry[4]={1,-1,0,0};
char _hex[16][4]={  '0','0','0','0',
                    '0','0','0','1',
                    '0','0','1','0',
                    '0','0','1','1',
                    '0','1','0','0',
                    '0','1','0','1',
                    '0','1','1','0',
                    '0','1','1','1',
                    '1','0','0','0',
                    '1','0','0','1',
                    '1','0','1','0',
                    '1','0','1','1',
                    '1','1','0','0',
                    '1','1','0','1',
                    '1','1','1','0',
                    '1','1','1','1',
};
int _bin[maxh][maxw],mmap[maxh][maxw];
int h,w;
vector<set<int>>lt;//存放连通块，而每个黑色连通块存放白色连通块的标号，防止重复计算
bool judge(int r,int c){
    if(r<0||c<0||r>=h||c>=w) return false;
    return true;
}
void hex_to_Binary(char ch,int row,int col){//十六进制转二进制，四位表示
    int idx;
    if(ch>='0'&&ch<='9')idx=ch-'0';
    else idx=ch-'a'+10;
    for(int i=0;i<4;i++){
        _bin[row][col+i]=_hex[idx][i]-'0';
    }
    return ;
}
void dfs(int row,int col,int num){//建立连通块
    mmap[row][col]=num;
    for(int i=0;i<4;i++){
        int r=row+dirx[i];
        int c=col+diry[i];
        if(judge(r, c)&&_bin[r][c]==_bin[row][col]&&!mmap[r][c])
            dfs(r, c, num);
    }
    return ;
}
void find_blank(int row,int col){//寻找此黑边附近有的白边数目
    for(int i=0;i<4;i++){
        int r=row+dirx[i];
        int c=col+diry[i];
        if(judge(r, c)&&_bin[r][c]==0&&mmap[r][c]!=1){//且不是最外的白边
            lt[mmap[row][col]].insert(mmap[r][c]);
            //对于此点的附近的白边，插入，并且不可以重复计算，所以用了set
        }
    }
    return ;
}
char image(int num){//根据黑边附近白边的数目来输出答案
    int cnt=lt[num].size();
    return s[cnt];
}
int main() {    
    int kase=1;
    while(scanf("%d%d",&h,&w)!=EOF){
        if(!h||!w)  break;
        memset(_bin,0,sizeof(_bin));
        memset(mmap,0,sizeof(mmap));
        printf("Case %d: ",kase++);
        
        //读入
        char line[maxw];
        for(int i=0;i<h;i++){
            scanf("%s",line);
            for(int j=0;j<w;j++){
                hex_to_Binary(line[j], i+1, j*4+1);
            }
        }
        
        h+=2;
     //外围加了一圈白色的背景，用作空白1，若不加这一圈，会无法判断白色在黑色内部还是外部。
        w=w*4+2;
        
        
        //建图
        int cnt=0;
        vector<int>blank;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(!mmap[i][j]){
                    dfs(i,j,++cnt);
                    if(_bin[i][j]==1)blank.push_back(cnt);
                }
            }
        }
        
        lt.clear();
        
        //找空白，求字母
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(_bin[i][j]==1)
                    find_blank(i, j);
            }
        }
        
        //答案整理输出
        vector<char>ans;
        for(int i=0;i<blank.size();i++){
            ans.push_back(image(blank[i]));//每个黑连通块求字母
        }
        sort(ans.begin(),ans.end());
        
        for(int i=0;i<ans.size();i++)
            printf("%c",ans[i]);
        printf("\n");
        
    }
    return 0;
}

后记

突破口：
1.敏锐的洞察力，寻找区别的突破口
2.将需要完成的事情，模块化，更加有利于整理思路，代码也更容易书写，也更容易debug。

还需锻炼读题能力，多读英文题目和题解。加快理解题目的速度，少用Google。

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽