UVA 1103 Ancient Messages 解题报告深度优先遍历

65 阅读 0 评论 43 点赞

我是靠谱客的博主威武白羊，最近开发中收集的这篇文章主要介绍UVA 1103 Ancient Messages 解题报告深度优先遍历，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

深度优先遍历

对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。

题目大意：

多组样例输入

每组输入样例中，第一行输入两个整数row、column，分别表示行数和列数。接下来输入

row行column列的十六进制字符矩阵picture（我的代码里变量名，下同），将其转为二进制矩阵pixel后（如 9c -->10011100），字符1表示一个黑色像素，字符0表示一个白色像素。最后通过其形状，依照图例按字典序输出该字符矩阵含有的所有古代象形符号（符号可重复）。

思路：

和其他题解的思路一致，先将该十六进制的字符矩阵转化为二进制矩阵，并且为其外围添上一圈白色像素（至于为什么需要加一圈白边，可以参考博客最后给出的第一组测试样例）如

接下来就是这个题的核心，需要用到DFS深搜。

根据提示，可以根据字符形成的白洞个数判断是什么字符。而在一个输入的矩阵中，可能有不止有一个连通块（即表示结果可能为多个象形文字符号），所以要先针对其中一个连通块的进行处理。 即第一次DFS：从pixel矩阵中任一黑色像素（字符‘1’）出发，对上下左右的字符DFS，遇’0‘返回，遇’1‘继续操作、将该字符拷贝到DFS_fb矩阵中（我的代码中的变量名）并且将原矩阵该位置进行区别标记（这样在找下一个连通块时，不会重复）。

结束后，就要针对DFS_fb矩阵寻找有多少个“洞”，即第二次DFS：从白色像素（字符‘0’）出发对上下左右的字符DFS，遇‘1’返回，遇‘0’继续执行操作并且进行区别标记（防止重复访问栈溢出），最后将查询到的‘洞’数目减一（因为我在DFS_fb矩阵中也加了白圈），进行multiset映射得到答案。

另外这个题细节也挺多的，比如十六进制转二进制、深搜时判断边界、打标记，需要注意。

#include <iostream>                 // Uva 1103
#include <map>
#include <set>
#include <cstring>
using namespace std;

char picture[251][251], pixel[251][251], DFS_fb[251][251];
int cnt, row, column;
multiset <char> ans;    // 将符号放入multiset容器内
map<char, string>transfor = {//把十六进制转换成二进制
		 {'0',"0000"}, {'1',"0001"}, {'2',"0010"}, {'3',"0011"},
		 {'4',"0100"}, {'5',"0101"}, {'6',"0110"}, {'7',"0111"},
		 {'8',"1000"}, {'9',"1001"}, {'a',"1010"}, {'b',"1011"},
		 {'c',"1100"}, {'d',"1101"}, {'e',"1110"}, {'f',"1111"}};

map<int, char>f = {{1,'A'}, {3,'J'},
				   {5,'D'}, {4,'S'},
				   {0,'W'}, {2,'K'}};

void Translate(char ch, int r)  // 十六转二，绘制像素图
{	
	pixel[r][0] = '0';
	pixel[r][4 * column + 1] = '0';

	if (ch >= '0' && ch <= '9')
		for (int i = 0; i < 4; i ++)
			pixel[r][cnt++] += transfor[ch][i];
	else if(ch >= 'a' && ch <= 'f')
		for (int i = 0; i < 4; i ++)
			pixel[r][cnt++] += transfor[ch][i];
}

void DFS_Find_Black(int r, int c, int lyb)
{
	if (r < 0 || r > row + 1 || c < 0 || c > 4 * column + 2)
		return;
	if (pixel[r][c] == '1' )     //如果是黑色像素 DFS
	{
		pixel[r][c] = '2' + lyb;   // 将已经拷贝的黑色像素设为非0字符。防止后面再一次被DFS调用
		DFS_fb[r][c] = '1' ;   
		DFS_Find_Black(r + 1, c, lyb);
		DFS_Find_Black(r - 1, c, lyb);
		DFS_Find_Black(r, c + 1, lyb);
		DFS_Find_Black(r, c - 1, lyb);
	}
	else
		return;
}

void DFS_Find_White(int r, int c)  // 针对于一个连通块进行DFS标记
{
	if (r < 0 || r > row + 1 || c < 0 || c > 4 * column + 2)
		return;
	if (DFS_fb[r][c] == '0')      // 将遍历过的白色像素标记为'2'
	{
		DFS_fb[r][c] = '2';
		DFS_Find_White(r + 1, c);
		DFS_Find_White(r - 1, c);
		DFS_Find_White(r, c + 1);
		DFS_Find_White(r, c - 1);
	}
	else
		return;
}
int main()
{
	int kase = 0;
	while (cin >> row >> column && row && column)
	{
		ans.clear();
		cout << "Case " << ++kase << ": ";
		int lyb = 0, holl = -1;
		memset(pixel, 0, sizeof(pixel));
		memset(picture, 0, sizeof(picture));
		memset(DFS_fb, '0', sizeof(DFS_fb));
		for (int i = 0; i < row; i++)     // 输入字符矩阵
			cin >> picture[i];

		for (int i = 0; i <= row; i++)
		{
			cnt = 1;
			for (int j = 0; j < column; j ++)
				Translate(picture[i][j], i+1);
		}

		for (int i = 1; i <= row; i++)
		{
			for (int j = 1; j <= 4*column; j++)
			{
				// 处理的是一整个黑色连通块，即为一个象形文字
				if (pixel[i][j] == '1')  // 如果是'1'的操作，（未处理过的黑色像素）。
				{
					DFS_Find_Black(i, j, lyb);  // 第一次DFS，只将该一个连通块拷贝到DFS_fb里，
					for (int i = 0; i <= row+1; i++)   // 第二次DFS, 在DFS_fb里查找有几个"白洞"
						for (int j = 0; j <= 4 * column+1; j++)
							if (DFS_fb[i][j] == '0')  // 在拷贝的DFS_fb里若遍历到'0'，则进行DFS
							{
								DFS_Find_White(i, j);  // 该操作进行一次，会使DFS_fb内一整个白色连通块标记变为 '2'
								holl++;
							}
					ans.insert(f[holl]);
					holl = -1;
				}			
				else
					continue;
				memset(DFS_fb, '0', sizeof(DFS_fb));
				lyb++;     // 在处理下一个黑色连通块时，给黑色设为另一个标记。
			}
		}
		for (auto p = ans.begin(); p != ans.end(); p++)
			cout << *p;
		cout << endl;
	}
}