数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C/C++中的数字连线游戏？
游戏规则 - 假设有一个n×n的方格数组。其中一些方格是空的，一些是实心的，一些非实心的方格由整数1、2、3……设置。每个整数在棋盘上占据两个不同的方格。玩家的任务是借助一条简单的路径（仅实现水平和垂直移动）连接棋盘上每个整数的两个出现位置。不允许两条不同的路径相互交叉。任何路径都不能包含任何实心方格（实心方格不允许出现在任何路径上）。最后，所有非实心方格必须由路径填充。
算法 - 为了构建具有给定棋盘大小n×n的有效随机谜题，我们首先在棋盘上生成随机的简单且互不相交的路径。如果一些孤立的方格位于所有生成的路径之外，则将这些孤立的方格标记为实心（禁止）。接下来，我们提供路径的端点以及实心方格的列表作为谜题。
因此，我们首先生成一个解决方案，然后根据解决方案制定谜题。路径和实心方格划分或分割n×n棋盘。我们实现了一个并查集数据结构来生成此分区。该数据结构处理棋盘上n^2个方格集合的子集。
伪代码
在棋盘上随机定位方格(a, b)和(c, d)，条件是 -
(a, b)和(c, d)彼此相邻，并且
(a, b)和(c, d)都不属于迄今为止生成的任何路径。如果在整个棋盘上找不到这样的方格对，则返回FAILURE /* 这里，(a, b)和(c, d)是将要构建的新路径上的前两个方格。 */
合并包含(a, b)和(c, d)的两个并查集树。
重复以下操作，直到当前路径可以扩展 -
重命名(a, b) = (c, d)。
定位(a, b)的一个随机相邻方格(c, d)，条件是 -
(c, d)不属于迄今为止生成的任何路径（包括当前路径）
在部分构建的当前路径上，(c, d)唯一的邻居是(a, b)。
如果找不到这样的邻居(c, d)，则该路径无法进一步扩展，因此退出循环
否则，合并(a, b)和(c, d)所属的两个并查集树。
设置新路径起点和终点两个方格的端点标志。
返回SUCCESS
165 次查看
