資料結構
網路
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 次檢視
