python - 在python中的二维列表中对邻居进行分组

Question

我有一个 2D 列表，它是一个游戏板，其中包含一个空白空间，它是一个点 (.)、一个“x”或一个“o”。我还有一个名为 groups = [] 的列表，此列表中的每个元素都是另一个列表(组)，该列表将包含 n 个列表，其中每个列表如下所示:[x, y](x 和y 坐标)。

一个组只由 o 或 x 组成。一个组可能只有一个石头(x 或 o)。如果一 block 石头有一个或多个连接，它就属于一个组。连接是石头(例如 x)在它旁边(x - 1，x + 1)或上面/下面(y - 1，y)具有相同“颜色”(x - 黑色，o - 白色)的石头+ 1).这是一个 4x4 板示例。

[['x', 'x', '.', 'x'],
 ['x', '.', '.', '.'],
 ['.', '.', '.', '.'],
 ['x', 'x', '.', '.']]

这里看起来像这样:

groups = [ [ [0, 0], [1, 0], [0, 1] ], [ [0, 3], [1, 3] ], [ [3, 0] ] ]

我想出了一个代码，它可以工作但效率不够高。另外，如果我对问题的解释不够好，请发表评论，我会尝试进一步解释。这是我想出的代码:

    if len(cells) > 0:
        while len(niezuzyte) != 0:   
            grupa = [niezuzyte[0]]
            zuzyte.append(niezuzyte[0])
            niezuzyte = [x for x in cells if x not in zuzyte]
            for ziomek in grupa:
                for cel in cells:
                    if abs(cel[0] - ziomek[0]) <= 1 and abs(cel[1] - ziomek[1]) <= 1:
                        if abs(cel[0] - ziomek[0]) + abs(cel[1] - ziomek[1]) < 2 and cel not in grupa:
                                zuzyte.append(cel)
                                grupa.append(cel)
                do_wyjeby.append(grupa)
                niezuzyte = [x for x in cells if x not in zuzyte]

列表名称很精致，但我希望它不会太重要，单元格是一组，其中包含板上所有 x'es 或 o's 的索引。该代码还为我提供了 [y, x] 组而不是 [x, y] 但这应该没什么大不了的。任何提示/帮助将不胜感激，谢谢!

Answer 1

您正在寻找连接组件的标签，该标签由 scikit-image 等提供。 .首先将您的列表变成一个数组:

import numpy as np
board = np.array([
    ['x', 'x', '.', 'x'],
    ['x', '.', '.', '.'],
    ['.', '.', '.', '.'],
    ['x', 'x', '.', '.']
])

您可以通过屏蔽该颜色并获取 labels 来获取给定“颜色”的连通分量为此:

from skimage.measure import label
labels, count = label(board == 'x', return_num=True, connectivity=1)

您可以使用 np.argwhere 将坐标提取为您想要的格式:

groups = [np.argwhere(labels == x) for x in range(1, count + 1)]

要获取 o 的坐标，请执行相同的操作，但对于 board == 'o'。请记住，此处的数据格式对于索引不是特别有用，因此除非您有一些特定的分析，否则您可能会考虑其他格式。

如果您想要混合 x 和 o 数据，skimage.measure.label 将正确标记整数图像中的任何不同区域。例如:

board = np.array([
    ['x', 'x', '.', 'x'],
    ['x', '.', '.', '.'],
    ['.', 'o', 'o', 'o'],
    ['x', 'x', '.', '.']
])
iboard = np.zeros_like(board, dtype='uint8')
iboard[board == 'x'] = 1
iboard[board == 'o'] = 2
labels, count = label(iboard, return_num=True, connectivity=1)

现在 labels 看起来像这样:

array([[1, 1, 0, 2],
       [1, 0, 0, 0],
       [0, 3, 3, 3],
       [4, 4, 0, 0]])

然后您可以使用 np.argwhere 一次将理解应用于所有标签。