6_13古代象形符号（UVa1103）<图的连通块的应用>
给出一幅黑白图像，每行相邻的四个点压缩成一个十六进制的字符。然后还有题中图示的6中古老的字符，按字母表顺序输出这些字符的标号。
输出说明：
For each test case, display its case number followed by a string containing one character for each
hieroglyph recognized in the image, using the following code:
Ankh: A
Wedjat: J
Djed: D
Scarab: S
Was: W
Akhet: K
Sample Input
100 25
0000000000000000000000000
0000000000000000000000000
...(50 lines omitted)...
00001fe0000000000007c0000
00003fe0000000000007c0000
...(44 lines omitted)...
0000000000000000000000000
0000000000000000000000000
150 38
00000000000000000000000000000000000000
00000000000000000000000000000000000000
...(75 lines omitted)...
0000000003fffffffffffffffff00000000000
0000000003fffffffffffffffff00000000000
...(69 lines omitted)...
00000000000000000000000000000000000000
00000000000000000000000000000000000000
0 0
Sample Output
Case 1: AKW
Case 2: AAAAA
解题思路：本题给出了一张图片的16进制的编码，要求找出这张图片中出现的符号。解码成二进制字符串后，实际上就是用普通的dfs解决了，不过如何进行dfs是本题的关键。
分析:
首先图像是被压缩过的，所以我们要把它解码成一个01矩阵。而且我们还要在原图像的四周加一圈白边，这样图中的白色背景都连通起来了。
黑色连通块的个数就是字符的个数。
观察题中字符样式可知，每种字符中包裹的“白洞”的个数是不同的，所以我们可以根据每个字符中的“白洞”的个数来区别这些字符。
思路大致可以这样描述：
1. 将16进制的图转换成2进制的图（起点坐标为（1，1）），1表示黑色，0表示白色
2. 先给图的外围加一层0的外壳， 然后从（0，0）开始深搜一遍0的连通块，并将每个点标记成标记成2
3. 经过2操作后剩下的0全是字符内的洞了，然后开始扫描图中为1的点，标记成3，同时，若扫描到的1点旁边有0点，则深搜0的连通块，标记成4
4. 在进行3时，同时计数扫描1这个连通块所能搜到的0的连通块的个数，从而得到对应的字符，加入到ans数组中，如此便得到了答案
最新文章
- Codeforces Round #375 (Div. 2) F. st-Spanning Tree
- 嵌入式Linux的调试技术
- android快速入门
- dp和px的转换
- Mysql 按行dump出数据
- 王家林 大数据Spark超经典视频链接全集[转]
- Qt5 添加右键菜单简单测试
- SQLite入门与分析(三)---内核概述(2)
- Linux用户空间与内核空间
- ORA-12012 error on auto execute of job 8887
- 当JAVA集合移除自身集合元素时发生的诸多问题
- UVA - 10118Free Candies（记忆化搜索）
- DNA和纳米（Nano）Fusion技术的发展趋势
- IT行业歧视40岁以上人群为找工作还要谎报年龄[转]
- Dev控件treeList
- javascript中事件对象注册与删除
- STL中vector、set、list和map
- BZOJ4036 [HAOI2015]按位或 FWT
- Alpha冲刺——序言篇(任务与计划)
- springboot系列十、springboot整合redis、多redis数据源配置