在二维列表中查找包围组

Question

我想通过一个小项目来消除我的 python 能力，但我遇到了问题。 作为上下文，我正在尝试在 tkinter 中制作一款围棋游戏。我使用二维列表来表示板，然后显示它。黑色棋子表示为

1

，白色棋子表示为

2

，

0

表示空白（示例如下）。 名单：

board = [[0, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 2, 2, 0, 2, 0, 0, 0],
         [0, 2, 2, 1, 2, 0, 0, 0, 0],
         [2, 2, 1, 1, 1, 2, 2, 2, 0],
         [1, 1, 1, 0, 1, 1, 1, 2, 2],
         [0, 0, 0, 0, 0, 0, 2, 1, 1],
         [0, 0, 0, 0, 1, 0, 1, 0, 0],
         [0, 1, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 0]]

代表这个

问题是，我不知道如何处理被包围/死亡的群体。 以这个板为例：

[[0, 2, 2, 0, 0],
 [2, 1, 1, 2, 0],
 [2, 2, 1, 2, 0],
 [0, 0, 2, 0, 0],
 [0, 0, 0, 0, 0]]

我想得到：

[[0, 2, 2, 0, 0],
 [2, 0, 0, 2, 0],
 [2, 2, 0, 2, 0],
 [0, 0, 2, 0, 0],
 [0, 0, 0, 0, 0]]

如果

1

替换

2

则相同，反之亦然。 我想从随机的空点进行洪水填充，看看哪些组会留下来，但是一排活石头可以像这样阻止洪水（用

9

代表被淹没的部分）：

[[0, 0, 2, 9, 9],
 [0, 1, 1, 2, 9],
 [2, 2, 1, 2, 9],
 [9, 9, 2, 9, 9],
 [9, 9, 9, 9, 9]]

我们什么都不知道了。我的一个想法是让洪水影响每个值，并且运行它可能只留下封闭的组。它只会影响第一个“层”，除非该组是开放的（我不知道这是否有意义）。我尝试摆弄我计算机上的此填充版本，但无法使其工作。关于如何解决这个问题我没有任何其他想法。 使用此post的解决方案会在该板上留下一个错误，例如：

[[0, 1, 0],
 [1, 2, 1],
 [0, 2, 0]]

给予：

[[0, 1, 0],
 [1, 3, 1],
 [0, 2, 0]]

但是中间的石头并没有死...

非常欢迎任何帮助！

Answer 1

实现目标的一种方法是：

from typing import List, Set, Tuple

def is_valid_coord(coord: Tuple[int, int], size: int) -> bool:
    x, y = coord
    return 0 <= x < size and 0 <= y < size

def get_neighbors(coord: Tuple[int, int]) -> List[Tuple[int, int]]:
    x, y = coord
    return [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]

def find_group(coord: Tuple[int, int], board: List[List[int]], visited: Set[Tuple[int, int]]) -> List[Tuple[int, int]]:
    group = []
    color = board[coord[0]][coord[1]]
    stack = [coord]

    while stack:
        current = stack.pop()
        if current not in visited:
            visited.add(current)
            group.append(current)
            neighbors = get_neighbors(current)
            for neighbor in neighbors:
                if is_valid_coord(neighbor, len(board)) and board[neighbor[0]][neighbor[1]] == color:
                    stack.append(neighbor)

    return group

def remove_dead_groups(board: List[List[int]]) -> List[List[int]]:
    size = len(board)
    visited = set()
    new_board = [[stone for stone in row] for row in board]

    for x in range(size):
        for y in range(size):
            coord = (x, y)
            if board[x][y] != 0 and coord not in visited:
                group = find_group(coord, board, visited)
                liberties = set()

                for stone_coord in group:
                    neighbors = get_neighbors(stone_coord)
                    for neighbor in neighbors:
                        if is_valid_coord(neighbor, size) and board[neighbor[0]][neighbor[1]] == 0:
                            liberties.add(neighbor)

                if all(is_valid_coord(neighbor, size) and board[neighbor[0]][neighbor[1]] != 0 for neighbor in liberties):
                    for stone_coord in group:
                        new_board[stone_coord[0]][stone_coord[1]] = 0

    return new_board

然后，如果你要像这样测试它：

board_1 = [
    [0, 2, 2, 0, 0],
    [2, 1, 1, 2, 0],
    [2, 2, 1, 2, 0],
    [0, 0, 2, 0, 0],
    [0, 0, 0, 0, 0]
]

board_2 = [
    [0, 1, 0],
    [1, 2, 1],
    [0, 2, 0]
]

new_board_1 = remove_dead_groups(board_1)
for row in new_board_1:
    print(row)

print()

new_board_2 = remove_dead_groups(board_2)
for row in new_board_2:
    print(row)

您应该得到以下结果：

[0, 2, 2, 0, 0]
[2, 0, 0, 2, 0]
[2, 2, 0, 2, 0]
[0, 0, 2, 0, 0]
[0, 0, 0, 0, 0]

[0, 1, 0]
[1, 2, 1]
[0, 2, 0]