0과 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

도움이 되셨기를 바라며 추가 질문이 있는 경우 댓글을 남겨주세요. : )