如何在 0 和 1 的网格中识别等腰三角形？

debugcn 发表于 Dev

佩顿

考虑一个由随机 0 和 1 组成的 10 * 10 大小的网格。我想确定网格中最高级别的等腰三角形

网格：

1 1 0 1 1 1 1 1 1 1

1 1 1 1 1 1 0 1 1 1

1 1 1 1 0 1 0 1 1 1

1 0 1 1 1 1 1 1 1 1

1 1 1 0 1 0 0 1 1 1

1 1 0 1 1 1 1 1 1 1

0 1 1 1 1 1 1 1 0 0

1 1 1 0 1 1 1 1 0 1

1 1 1 1 1 1 1 1 0 1

1 1 1 1 1 1 1 1 0 1

预期输出：

三角形的最高层为 3

雷克纳克

我假设只找到三角形向上方向，所有1或全部0。如：

    1         
  1 1 1       0 
1 1 1 1 1   0 0 0

您可以从顶点开始，找到backtracking我在中实现的最大三角形 by ，find_max_triangle然后遍历所有矩阵，并从它的每个点开始。

我们可以通过跳过一些点来减少遍历时间。优化是通过当前的 max_level 修剪 i, j：

def max_triangles(matrix):
    m, n = len(matrix), len(matrix[0])
    max_level = 1

    def find_max_triangle(x, y, v):
        nonlocal max_level
        cur_level = 1
        while True:
            x += 1
            if x == m:
                return
            for i in range(-cur_level, cur_level + 1):
                _y = y + i
                if _y < 0 or _y >= n or matrix[x][_y] != v:
                    return
            cur_level += 1
            max_level = max(max_level, cur_level)

    for i in range(m):
        # optimization: pruning i by current max_level
        if i + max_level >= m:
            break
        for j in range(n):
            # optimization: pruning j by current max_level
            if j - max_level >= 0 and j + max_level < n:
                find_max_triangle(i, j, matrix[i][j])

    return max_level

测试和输出：

matrix = [[1, 1, 0, 1, 1, 1, 1, 1, 1, 1],
          [1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
          [1, 1, 1, 1, 0, 1, 0, 1, 1, 1],
          [1, 0, 1, 1, 1, 1, 1, 1, 1, 1],
          [1, 1, 1, 0, 1, 0, 0, 1, 1, 1],
          [1, 1, 0, 1, 1, 1, 1, 1, 1, 1],
          [0, 1, 1, 1, 1, 1, 1, 1, 0, 0],
          [1, 1, 1, 0, 1, 1, 1, 1, 0, 1],
          [1, 1, 1, 1, 1, 1, 1, 1, 0, 1],
          [1, 1, 1, 1, 1, 1, 1, 1, 0, 1]]

print(max_triangles(matrix))

# output 3

希望能帮到你，还有什么问题可以评论。:)

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。