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
