python - 检查一系列二进制状态

Question

我认为解释这一点的最简单方法是使用井字游戏的类比。棋盘可以表示为二进制状态的二维数组。

所以板号可以显示为 [[1,2,3],[1,2,3],[1,2,3]]该数组的每个索引都有一个二进制值(X 或 O)因此，要检查玩家是否获胜，您需要检查获胜图案中的所有 3 个方 block 是否共享相同的状态。

现在，在这个类比中，您可以对获胜的解决方案进行硬编码，并让董事会独立对其进行检查，但在我的情况下，我不想对它们进行硬编码，因为我需要(最终)在运行。因此，目前我只能手动检查或硬编码它们，但我需要找到一种方法来检查这些模式，而无需硬编码解决方案。

这是我目前举的最小数组:

[[[1,a], [2,a], [3,a]],
 [[3,a], [1,a], [2,a]],
 [[1,a], [2,a], [3,a]]]

现在“a”是空白状态，它将被“b”或“c”(或任意两个指定)替换，并且 1、2 和 3 表示“行”。

展示这一点的视觉方式可以被视为:

看到“线”如何相互交叉了吗？这个数组中的模式是:

• 水平任意 3 个
• 任何 3 个位于一条“线”上(不是笔直向上且向下)
• 以及row 1 line 1, r2l2, r3l3 & r1l3的具体模式，r2l2，r3l1

在较大的数组中，有更多的模式，但这是我能做的最简单的。

任何人都可以帮我找到一个解决方案来查找生成的模式，以便我可以检查它们的状态吗？我正在用 python 测试这个，但我也可以使用纯数学解决方案

Answer 1

一种方法是逐行扫描网格，并为每个位置跟踪所有可能方向上的图案长度。在这种情况下，方向将是左上 -> 右下、右上 -> 左下、左 -> 右并沿着“线”。处理每个位置时，如果状态匹配，则将先前模式的值增加 1，否则将值设置为 0。只要找到目标长度或网格已完全迭代，就停止。

这是上面的一个简短示例，其中单元格具有二元状态:

grid = [
    [[1, 0], [2, 0], [3, 1]],
    [[3, 1], [1, 0], [2, 0]],
    [[1, 0], [2, 0], [3, 1]]
]

def find(g, length):
    # Top left -> bottom right, top right -> bottom left
    # and left -> right lengths are stored here
    prev = [[0] * 3 for _ in xrange(len(g[0]))]
    # 'Line' length is stored here for efficiency
    prev_line = {}
    for row in grid:
        cur = []
        cur_line = {}
        for i in xrange(len(row)):
            tl = line = tr = left = 0
            if row[i][1] == 1:
                # Up left
                tl = 1 + (prev[i-1][0] if i else 0)
                # Line
                line = 1 + prev_line.get(row[i][0], 0)
                # Up right
                tr = 1 + (prev[i+1][1] if i < len(row) - 1 else 0)
                # Straight Left
                left = 1 + (cur[i-1][2] if i else 0)

            if any(x == length for x in (tl, line, tr, left)):
                return True
            cur.append([tl, tr, left])
            cur_line[row[i][0]] = line

        prev = cur
        prev_line = cur_line

    return False

find(grid, 3) # True