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数组中,如此便得到了答案

原文地址:https://www.cnblogs.com/jjzzx/p/5548372.html