确定一个给定的点是否会产生一个岛

Question

我目前正在使用GBDK将游戏三里，也就是单曲移植到C中的game。这个游戏的规则之一是，董事会的任何区域都不能与其他区域完全关闭。例如，如果董事会的当前状态是：

00100

01000

00000

00000

00000

解决方案不能包含1 at (0,0)或(0,2)。板的生成功能需要能够检测到这一点，而不是放置在那里的黑色瓷砖。我目前使用的非递归深度优先搜索，这是可行的，但在更大的板上非常缓慢。我在互联网上找到的这个游戏的所有其他实现都使用DFS。游戏男孩太慢了。

我需要的是一种算法，当给定一个坐标时，可以判断是否可以在不分割板的情况下将1放在那个位置。我已经研究过基于扫描线的填充算法，但我不确定它们的速度会有多快，因为板中很少有长的水平线。我还想用算法沿着边走，但我认为如果边没有连接到板的一侧，那就失败了：

00000

00100

01010

00100

00000

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

Answer 1

我看了另一个生成器代码，它反复选择一块瓷砖来考虑变黑，如果这样做不会导致一个无效的板。如果您的生成器以同样的方式工作，我们可以利用连接查询的相关性。生成的算法将需要O(n平方)-time初始化，然后在摊销的O(log )时间内处理每个更新(如果您实现平衡的不相交集合合并，实际上是逆Ackermann )。虽然n= 15很小，但随着算法的进行，常数应该是可以的。

将板看作是去掉黑砖的网格图的子集，我们需要检测连通分量的数量何时会从1增加。借用我的同事JakubŁącki和Piotr Sankowski (“平面图中的最优递减连通性”，引理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，那么就可以将face a与face b连接起来。这是工作中的平面二元性。我们已经把原始的一个困难的衰老问题变成了对偶中的增量问题！这个增量问题可以用Kruskal算法中的方法，通过不相交的集合数据结构来解决。

为了显示这是如何工作的，假设我们黑了6。那么这个图表会是这样的：

1-2-3
|a|
4-5
|c|
7-8-9 i

这个图有V=8，E=9和F= 3，所以V 2 E+F= 2。如果去掉3，则顶点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()