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

Question

考虑一个由随机 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

Answer 1

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

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

你可以从顶部开始，通过backtracking找到最大三角形，我在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

希望对您有所帮助，如果您有其他问题，请发表评论。