扫雷大师：用C语言揭秘自动展开盘面与智能扫雷策略

扫雷

扫雷游戏是一款经典的单人电脑游戏，其主要规则如下：

游戏目标：游戏的目标是在不触发任何地雷的情况下，找出所有非雷区域。玩家需要根据格子周围的数字来推断哪些格子含有地雷。
游戏界面：游戏界面是一个由许多封闭的格子组成的方形网格。格子的数量根据游戏难度不同而变化。一些格子下藏有地雷，其余格子则不含地雷。
操作方式：
- 左键点击一个格子会打开它，如果该格子下藏有地雷，则游戏结束。如果点击的格子周围没有地雷，则会显示一个数字，这个数字表示该格子周围八个格子中有多少个是地雷。
- 如果点击的格子周围没有地雷，游戏会自动展开与该格子相邻的区域，直到显示出周围有地雷的格子为止。
- 右键点击一个格子可以标记一个地雷的位置，防止误触。玩家也可以再次右键点击来取消标记或标记为问号。
胜利条件：玩家揭示所有非雷区域而没有触发任何地雷时，游戏胜利。
计时和计分：大多数扫雷游戏都会计时，玩家完成游戏所需的时间越短，成绩就越好。有些版本的游戏还会根据不同的标准进行计分。

这些是扫雷游戏的基本规则，游戏的乐趣在于玩家需要运用逻辑和策略来避免地雷，同时尽可能快地清除非雷区域。

举个例子：假设有这么一个盘面。
在这里插入图片描述
注意我标注出来的那个1，这个1周围的8个位置只有1个雷，所以右下角那个位置必然是雷，可以标注出来。

此时注意右下方那个1。

由于周围8个位置已经有1个位置确定是雷了，所以其余几个位置一定不是雷，也就是下面标注的位置都不是雷。
在这里插入图片描述
这样就可以接着展开这几个位置了。

如果使用C语言，我们用2个数组，其中一个数组mine存储雷的位置信息，用1表示雷，0表示非雷；另一个数组show存储展示给玩家的盘面，其中星号表示这个位置没有被排查，空格表示这个位置周围没有雷，数字字符标识周围雷的数量，标记位用感叹号和问号表示。注意为了防止潜在的越界，数组要比实际情况多开一圈，也就是说，如果是9*9的盘面，就应该开11*11的大小。

自动展开盘面

注意到如果周围有一大片非雷位置，有可能会一次性展开一片区域。这可以通过递归实现。

递归的结束条件：

这个位置已经越界了。
这个位置已经排查过了。
这个位置是雷。
这个位置周围有雷。

如果还没满足递归的结束条件，就递归探索上下左右四个位置。

void ExpandMine(char mine[ROWS][COLS], char show[ROWS][COLS], int x, int y)
{
	// 越界
	if (x < 1 || x > ROW || y < 1 || y > COL)
		return;

	// 排查过
	if (show[x][y] == ' ' || isdigit(show[x][y]))
		return;

	// 遇到雷
	if (mine[x][y] == '1')
		return;

	// 排查并展开
	int n = GetMineCnt(mine, x, y);
	show[x][y] = n == 0 ? ' ' : '0' + n;
	if (n == 0)
	{
		ExpandMine(mine, show, x - 1, y);
		ExpandMine(mine, show, x + 1, y);
		ExpandMine(mine, show, x, y - 1);
		ExpandMine(mine, show, x, y + 1);
	}
}

智能扫雷

说是智能扫雷，其实只是把一个新手扫雷玩家的简单想法交给电脑完成。那么一个新手是怎么想的呢？

如果一个盘面内，有某几个位置确定是雷了，新手玩家就会把它标记出来。比如：

在这里插入图片描述
注意到2个1周围只有1个位置可能是雷，那这个位置就一定是雷了。换句话说，如果某个数字和周围有可能是雷的位置数相等，那么这几个位置就一定是雷，可以标记。

option为0表示标记（鼠标右键），option为1表示排查（鼠标左键）。GetShowCnt返回（i，j）周围有几个字符在字符串中，GetShowPoint返回满足在字符串中的字符坐标。注意x和y都是int*类型的指针。

// 找到某个数字，恰好等于周围所有未排查的雷
for (int i = 1; i <= ROW; ++i)
{
	for (int j = 1; j <= COL; ++j)
	{
		if (isdigit(show[i][j])
			&& GetShowCnt(show, i, j, "*!") == show[i][j] - '0'
			&& GetShowCnt(show, i, j, "*"))
		{
			*x = i;
			*y = j;
			GetShowPoint(show, x, y, "*");
			*option = 0;
			return;
		}
	}
}

如果已经把确定是雷的位置都找出来了，接下来应该做什么呢？
在这里插入图片描述
注意到框起来的1，周围已经有一个位置确定是雷了，那么圈起来的位置就一定不是雷。换句话说，如果某个数字和周围确定是雷的位置数相等，则其余位置一定不是雷，可以排查。

// 找到某个数字，与周围已标记为!的位置数相等，其余位置排查
for (int i = 1; i <= ROW; ++i)
{
	for (int j = 1; j <= COL; ++j)
	{
		if (isdigit(show[i][j])
			&& GetShowCnt(show, i, j, "!") == show[i][j] - '0'
			&& GetShowCnt(show, i, j, "*"))
		{
			*x = i;
			*y = j;
			GetShowPoint(show, x, y, "*");
			*option = 1;
			return;
		}
	}
}

当然，如果既找不到确定是雷的位置，也找不到确定不是雷的位置，就只能随机排查了。

// 随机排查某一个位置
while (true)
{
	*x = rand() % ROW + 1;
	*y = rand() % COL + 1;
	if (show[*x][*y] == '*')
	{
		*option = 1;
		return;
	}
}

更优策略

其实，以上并不是最优策略，经过测试，当代码走到“随机排查”的时候，有很大概率会踩到雷。事实上，如果你是个扫雷新手，在遇到无法判断的情况时，乱点一通，是很有可能踩到雷的。

这里抛砖引玉，有没有更优的策略呢？

如果你是扫雷高手，应该会知道些定式。我们可以让计算机识别这些基础模式，从而在某些情况下也能给出最优解：

直线模式

1-2-1模式：当你在直线上看到1-2-1的排列时，两边的1对应的未揭开的格子都是雷。
1-2-2-1模式：在直线上，如果出现1-2-2-1的排列，最外侧的1旁边的未揭开的格子是雷，而2之间的格子不是雷。

方块模式

2x2的雷区：在一个2x2的区域内，如果有两个相邻的数字相同，那么他们共同指向的未揭开的格子是雷。

交叉模式

相交的1：如果两个1在角落相交，那么两个1共同指向的那个格子是雷。
相交的2：如果两个2在角落相交，且它们共有三个未揭开的格子，通常情况下，靠近两个2的两个格子是雷，远离2的那个格子不是雷。