arrays - 确定给定点是否会创建岛屿

Question

我目前正在努力移植游戏 Hitori, aka Singles使用 GBDK 到 C 语言的 Game Boy。这个游戏的规则之一是棋盘上的任何区域都不能与其他区域完全隔离。例如，如果棋盘的当前状态是:

00100
01000
00000
00000
00000

解在 (0,0) 或 (0,2) 处不能包含 1。板生成功能需要能够检测到这一点并且不在那里放置黑色瓷砖。我目前正在使用非递归深度优先搜索，它可以工作，但在较大的板上速度非常慢。我在互联网上找到的这个游戏的所有其他实现都使用 DFS。 Game Boy 太慢了。

我需要的是一种算法，当给定一个坐标时，它可以判断是否可以在不分割棋盘的情况下将 1 放置在该位置。我研究过基于扫描线的填充算法，但我不确定它们会快多少，因为板中很少有长水平线。我还考虑过使用一种算法来沿着边缘跟踪，但我认为如果边缘没有连接到板的侧面，那么就会失败:

00000
00100
01010
00100
00000

还有其他类型的算法可以有效地做到这一点吗？

Answer 1

我查看了另一个生成器代码，它反复选择一个图 block 来 考虑黑化，如果这不会导致板无效，就这样做。 如果您的生成器以相同的方式工作，我们可以利用以下相关性 连接查询。由此产生的算法将需要 O(n²) 时间初始化，然后以摊销方式处理每个更新 O(log n) 时间(如果实现平衡，实际上是逆阿克曼 不相交集合并)。随着算法的进行，常数应该没问题， 尽管 n = 15 很小。

将棋盘视为带有黑色图 block 的网格图的子集 删除后，我们需要检测连接组件的数量何时会增加 从 1 开始增加。借用我的同事 Jakub Łącki 的一个想法， Piotr Sankowski(“平面图中的最优递减连通性”， 引理2)，我们可以利用欧拉特征和平面对偶来帮助 完成这个。

让我画一个空板(带有编号的图 block )及其网格图。

+-+-+-+
|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 脸。

通过使图 block 变黑，我们删除了它的顶点和相邻的边缘 从图中。这里有趣的是面孔上发生的事情。 例如，如果我们删除边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()