学习用品

数据结构实验题A(1)

题目分析:

只是空行用

本题存在一个关键条件:

若该方格未与地雷相邻(即该方格周围 8 个格子内没有地雷),则该方格的未被 打开的邻居(即与该方格上、下、左、右、左上、左下、右上、右下相邻的方 格)、邻居的邻居、邻居的邻居的邻居……都会被逐级打开,直到某方格与地雷 相邻。

这是一个由中心点不断向外扩散的过程,与BFS的算法一致。那么,本题的核心导向就明确了,通过对BFS的迁移应用写出核心算法。

那么该如何迁移改写呢?不妨采用伪码的形式思考。

void BFS()
{
	//记录当前节点值(领域雷数)
	当前节点值 = f(x, y); //f(x, y)函数为计算x行y列节点邻域雷数的函数
	
	//定义递归出口,邻接区域有雷
	if (当前节点值 != 0) return;
	
	//递归调用,计算邻域节点值
	BFS(左上结点);
	BFS(左结点);
	BFS(左下结点);
	BFS(下结点);
	BFS(右下结点);
	BFS(右结点);
	BFS(右上结点);
	BFS(上结点);
}

这是大概框架,如果真就这么填充完而不加限定条件肯定原地爆炸。

所以,要在递归调用前判定该邻接结点是否存在,若存在,才可以进行递归调用。

配合原先我定义的可变二维数组,可以比较容易搭建解题的基本框架。

附传送门: http://wavelet.xyz/index.php/2020/01/22/c%e5%ae%9e%e7%8e%b0%e5%8f%af%e5%8f%98%e9%95%bf%e5%ba%a6%e4%ba%8c%e7%bb%b4%e6%95%b0%e7%bb%84/

发表评论

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