UVA1103 题意分析加思路讲解,DFS,详细~

题目原文链接

题意：

很有意思的一道题，建议先去看完原文再回过头来看这篇博客。
大致意思是给出6种古埃及符号，输入一幅黑白图像的16进制表示，要求识别每幅图像中的符号并按照字典序输出。

6种古埃及符号如下图所示：

题目输入：

每组测试数据包含一个H行W列的字符矩阵$（H\le 200，W\le 50）$，每个字符为4个相邻的像素点的十六进制 （例如：字符$c$对应的四个像素点就是$1100$），转化为二进制后的$1$表示黑点，$0$表示白点。
且输入满足：

1. 不会出现上述6种符号以外的其他符号
2. 输入至少包含一个符号，并且输入的每一个黑点都属于一个符号
3. 每个符号的黑色像素都相互连接，并且不同的符号不会相互接触，也不会互相包含
4. 如果两个黑色素有公共的顶点，则它们i顶有一个相同的相邻黑像素
5. 符号的形状一定和上述中的图形拓补等价（即可以任意拉伸但是不能拉断）

输出

按照字典顺序输出每个字符的缩写，上述$6$个符号的缩写从左到右分别为 A J D S W K
例：输入下面图形的16进制表示，输出AKW

想要完全理解这道题的意思并不容易，你需要了解一点关于图像的知识。事实上，再复杂不过的图片，也可以拆分为两部分，一是图像的轮廓，二是图像的颜色。轮廓是二维平面上的点集，因而图像本质上就是二维平面上的一些带颜色点组成的集合，虽然在数学上点是无法定义的，它只有位置，而没有形状，但是我们却可以用一个足够小的区域去逼近一个点，然后区域的颜色就近似为这个点的颜色，这样我们就可以用这样一个近似的“点”去“画”图了。仔细一想，我们生活中用的铅笔，圆珠笔等不都是这样一个道理吗？
而在计算机中，这样一个近似的点其实就是所谓的像素点，也就是一个小小的矩形格子，每个格子都有一个颜色，就是所谓的像素点的颜色，为了存储方便，每一种颜色的像素点都用一个数值来表示。这样，图像在计算机中就可以表示为一个二维的矩阵。此处题目的输入正是采用了这样一种方式，由于这道题我们只关心图像的形状，故而只需要黑白（分别用1和0表示）两种颜色即可。
由于输入的符号可以随意拉伸，看起来我们不能拘泥于细节，而是要找到一个不会随着任意拉伸而变化的特征量。细品题目对于输入的描述，每个符号的所有黑色像素都相互连接，而不同的符号互相之间没有交集，即每个符号的黑像素点集都是一个连通集，中间有一些白色像素点组成的洞，数一数就能发现，6种符号从左往右依次有1，3，5，4，0，2个白洞，互不相同，可以作为我们判断符号的特征量。
进一步，我们可以利用每个符号的黑像素为连通集并且每个白洞也是一个连通集的特点，进行如下步骤判断符号：
１．首先给整幅图加上一层白色边框，使所有的非白洞白色像素点构成一个连通集
２.　DFS遍历所有非白洞像素点，全部标记为２
３.　检查图像中的黑色像素点，每次找到一个黑色像素点，DFS遍历该黑色像素点的连通集，并统计该符号的白洞的个数。
４．具体的计数白洞的个数的方法为：在DFS遍历黑色像素点周围的点时，如果发现有白色像素点，则该白色像素点一定为该符号的某个白洞内的点，DFS遍历该白洞，并将该白洞的所有点标记为２，然后白洞数加１。

具体代码如下：

#include <bits/stdc++.h>
using namespace std;
unordered_map<char,string> toBinary{	
	// 将16进制的字符转化为四位的二进制
	{'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> Res{	
	// 白洞数目 ---> 符号缩写
	{1,'A'},{3,'J'},{5,'D'},
	{4,'W'},{0,'S'},{2,'K'}
};
int move[][2] = {
	{1,0},{-1,0},{0,1},{0,-1}
}	
int H,W;
int cnt;
vector<string> image;
void dfs(int i,int j,char s,int & ans){
	image[i][j] = (char) image[i][j]+2;
	for(int k = 0; k < 4; ++k) {
		int ii = i + move[k][0];	// 周围位置
		int jj = j + move[k][1];
		if(ii < 0 || ii > image.size() || jj < 0 || jj > image[i].size()) continue;
		if(image[ii][jj]=='0' && s=='1') {	// 找到一个白洞
			ans++;
			dfs(ii,jj,'0',ans);
		}
		else if(s==image[ii][jj])	//  继续走连通区域
			dfs(ii,jj,s,ans);
	}
}
int main()
{
	string line;
	int kase = 0;
	while(scanf("%d %d",&H,&W) && H) {
		image.resize(H+2);
		// 加一层白边
		image.front() = string(4*W+2,'0');
		for(int i = 1; i <= H; ++i) {
			scanf("%s",line);
			image[i] = "0";
			for(char c:line) 
				image[i] += toBianry[c];
			imag[i] += "0";
		}
		image.back() = string(4*W+2,'0');
		cnt = 0;
		string result = "";	// 保存结果
		dfs(0,0,'0',ans);
		 for(int i = 0; i < image.size(); ++i)
		 	for(int j = 0; j < image[0].size(); ++j) {
				if(image[i][j] == '1') {
					cnt = 0;
					dfs(i,j,'1',cnt);
					result += Res[cnt];
			}
		}
		sort(result.begin(),result.end());
		printf("Case %d: %sn",++kase,result);
	}	
}

最后

以上就是幸福羽毛为你收集整理的UVA1103 题意分析加思路讲解,DFS,详细~的全部内容，希望文章能够帮你解决UVA1103 题意分析加思路讲解,DFS,详细~所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。