POJ 2386解题报告

之前在面试的时候被问到一个关于深度优先搜索的题目。后来在《挑战程序设计竞赛》书上看到了那道面试题的原型,这是POJ上的一道题目。

题目描述:

有一个大小为N*M的园子,雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼?(八连通指的是下图中相对W的*的部分)

***
*W*
***('W'表示积水,'.'表示没有积水)

题目分析:

要求出园子里总共有多少个水洼,就是求出园子里有多少个“连在一起”的'W',这些“堆”'W'彼此分隔,这里的连在一起指的是每个'W'在八个方向上总有一个方向能够使得和临近的'W'连接在一起,从而形成一个水洼。要算出这些水洼的数目,就需要访问所有节点直到遇到'W',然后判断这个'W'的八个方向上是否有'W',若有的话,则继续对这八个方向上的'W'进行同样的访问方法,直到访问到'.'为止则停止访问,然后返回到原始'W'的下一个八个方向上的'W',再对这个'W'执行同样的操作...;若没有则继续访问其他节点直到遇到下一个'W'或全部节点都访问过了则退出程序。这里我们为避免重复计算'W',会把访问过的'W'置为'.'。其实这整个节点访问过程就是一个深度优先搜索(DFS)过程。最后只要算出总过作了多少次DFS过程就能知道园子里有多少个水洼了。算法复杂度为O(N*M)。

Codes :


//输入
int N,M;
char field[N][M];    //园子形状

void dfs(int i,int j)
{
	field[i][j] = '.';  //先把'W'置为'.',避免重复访问
	//对八个方向上的节点进行访问
	for(int x = -1; x <= 1; x++)
	{
		for(int y = -1; y <= 1; y++)
		{
			int tmp_x = i+x,tmp_y = j+y;
			//避免节点坐标超出可表示范围
			if(tmp_x >= 0 && tmp_x < N && tmp_y >= 0 && tmp_y < N && field[tmp_x][tmp_y] == 'W')
			{
				dfs(tmp_x,tmp_y);
			}
		}
	}
}

int solve()
{
	int ans;
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			if(field[i][j] == 'W')
			{
				dfs(i,j);
				ans ++;
			}
		}
	}
	printf("%d\n",ans);
	return 1;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>