我目前正在使用 GBDK將游戲Hitori（又名 Singles）移植到 C 中的 Game Boy。這個游戲的規則之一是棋盤的任何區域都不能與其他區域完全隔離。例如，如果板的當前狀態是：
00100
01000
00000
00000
00000
解不能在 (0,0) 或 (0,2) 處包含 1。棋盤生成功能需要能夠檢測到這一點，而不是在那里放置黑色瓷磚。我目前正在使用非遞回深度優先搜索，它有效，但在較大的板上非常慢。我在互聯網上可以找到的這個游戲的所有其他實作都使用 DFS。Game Boy 太慢了。
我需要的是一種演算法，當給定坐標時，它可以判斷是否可以在不分割板的情況下將 1 放置在該位置。我研究了基于掃描線的填充演算法，但我不確定它們會快多少，因為電路板上很少有長水平線。我還想過使用一種演算法來跟蹤邊緣，但我認為如果邊緣沒有連接到板的側面，那將會失敗：
00000
00100
01010
00100
00000
有沒有其他型別的演算法可以有效地做到這一點？
uj5u.com熱心網友回復：
我查看了另一個生成器代碼，它反復選擇一個圖塊來考慮變黑，如果這不會導致無效板，則這樣做。如果您的生成器以相同的方式作業，我們可以利用連接查詢的相關性。生成的演算法將需要 O(n2) 時間初始化，然后在分攤 O(log n) 時間內處理每個更新（如果您實作平衡的不相交集合合并，實際上是逆阿克曼）。隨著演算法的進行，常量應該沒問題，盡管 n = 15 很小。
將電路板視為去除黑色瓷磚的網格圖的子集，我們需要檢測連接組件的數量何時會從 1 增加。借用我的同事 Jakub ??cki 和 Piotr Sankowski（“平面中的最佳遞減連通性”）的想法Graphs”，引理 2)，我們可以使用歐拉特性和平面對偶來幫助實作這一點。
讓我畫一個空板（帶有編號的瓷磚）及其網格圖。
- - -
|1|2|3|
- - -
|4|5|6|
- - -
|7|8|9|
- - -
1-2-3
|a|b|
4-5-6
|c|d|
7-8-9 i
在該曲線圖我已經字母的面（有限面a，b，c，d
和無限面i）。平面圖滿足公式 V ? E F = 2 當且僅當它是連通且非空的。您可以通過 V = 9 個頂點和 E = 12 個邊和 F = 5 個面來驗證這個確實如此。
通過黑化一個圖塊，我們從圖中移除了它的頂點和相鄰的邊。這里有趣的是面部會發生什么。2-5例如，如果我們移除邊，那么我們將面a與面連接起來b。這是在起作用的平面二元性。我們已經將原始中一個困難的遞減問題變成了對偶中的一個遞增問題！這個增量問題可以通過不相交的集合資料結構以與 Kruskal 演算法相同的方式解決。
為了說明這是如何作業的，假設我們變黑了6。然后圖形將如下所示：
1-2-3
|a|
4-5
|c|
7-8-9 i
這個圖有 V = 8 和 E = 9 和 F = 3，所以 V ? E F = 2。如果我們要洗掉2，那么頂點3是斷開的。生成的圖將具有 V = 7 和 E = 6 和 F = 2（c和i），但 V ? E F = 3 ≠ 2。
為了確保我沒有遺漏任何東西，這里有一個經過測驗的 Python 實作。我的目標是可讀性而不是速度，因為您要將其翻譯成 C 并對其進行優化。
import random
# Represents a board with black and non-black tiles.
class Board:
# Constructs an n x n board.
def __init__(self, n):
self._n = n
self._black = [[False] * n for i in range(n)]
self._faces = [[Face() for j in range(n - 1)] for i in range(n - 1)]
self._infinite_face = Face()
# Blackens the tile at row i, column j if possible. Returns True if
# successful.
def blacken(self, i, j):
neighbors = list(self._neighbors(i, j))
if self._black[i][j] or any(self._black[ni][nj] for (ni, nj) in neighbors):
return False
incident_faces = self._incident_faces(i, j)
delta_V = -1
delta_E = -len(neighbors)
delta_F = 1 - len(incident_faces)
if delta_V - delta_E delta_F != 2 - 2:
return False
self._black[i][j] = True
f = incident_faces.pop()
for g in incident_faces:
f.merge(g)
return True
# Returns the coordinates of the tiles adjacent to row i, column j.
def _neighbors(self, i, j):
if i > 0:
yield i - 1, j
if j > 0:
yield i, j - 1
if j < self._n - 1:
yield i, j 1
if i < self._n - 1:
yield i 1, j
# Returns the faces incident to the tile at row i, column j.
def _incident_faces(self, i, j):
return {self._face(fi, fj) for fi in [i - 1, i] for fj in [j - 1, j]}
def _face(self, i, j):
return (
self._faces[i][j]
if 0 <= i < self._n - 1 and 0 <= j < self._n - 1
else self._infinite_face
).rep()
# Tracks facial merges.
class Face:
def __init__(self):
self._parent = self
# Returns the canonical representative of this face.
def rep(self):
while self != self._parent:
grandparent = self._parent._parent
self._parent = grandparent
self = grandparent
return self
# Merges self and other into one face.
def merge(self, other):
other.rep()._parent = self.rep()
# Reference implementation with DFS.
class DFSBoard:
def __init__(self, n):
self._n = n
self._black = [[False] * n for i in range(n)]
# Blackens the tile at row i, column j if possible. Returns True if
# successful.
def blacken(self, i, j):
neighbors = list(self._neighbors(i, j))
if self._black[i][j] or any(self._black[ni][nj] for (ni, nj) in neighbors):
return False
self._black[i][j] = True
if not self._connected():
self._black[i][j] = False
return False
return True
# Returns the coordinates of the tiles adjacent to row i, column j.
def _neighbors(self, i, j):
if i > 0:
yield i - 1, j
if j > 0:
yield i, j - 1
if j < self._n - 1:
yield i, j 1
if i < self._n - 1:
yield i 1, j
def _connected(self):
non_black_count = sum(
not self._black[i][j] for i in range(self._n) for j in range(self._n)
)
visited = set()
for i in range(self._n):
for j in range(self._n):
if not self._black[i][j]:
self._depth_first_search(i, j, visited)
return len(visited) == non_black_count
def _depth_first_search(self, i, j, visited):
if (i, j) in visited:
return
visited.add((i, j))
for ni, nj in self._neighbors(i, j):
if not self._black[ni][nj]:
self._depth_first_search(ni, nj, visited)
def generate_board(n, board_constructor=Board):
deck = [(i, j) for i in range(n) for j in range(n)]
random.shuffle(deck)
board = Board(n)
return {(i, j) for (i, j) in deck if board.blacken(i, j)}
def generate_and_print_board(n):
black = generate_board(n)
for i in range(n):
print("".join(chr(9633 - ((i, j) in black)) for j in range(n)))
def test():
n = 4
boards = set(frozenset(generate_board(n, Board)) for i in range(1000000))
reference_boards = set(
frozenset(generate_board(n, DFSBoard)) for k in range(1000000)
)
assert len(boards) == len(reference_boards)
if __name__ == "__main__":
generate_and_print_board(15)
test()
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/347364.html