Python에서 가장 긴 행렬 경로 길이를 찾는 프로그램

이진 행렬이 있다고 가정합니다. 여기서 0은 빈 셀을 나타내고 1은 벽을 나타냅니다. 첫 번째 행의 빈 셀에서 시작하여 마지막 행의 빈 셀에서 끝나기를 원할 수 있습니다. 우리는 왼쪽, 오른쪽 또는 아래로 이동할 수 있습니다. 각 셀을 한 번만 방문할 수 있는 가장 긴 경로를 찾아야 합니다. 이것이 불가능하면 0을 리턴하십시오.

따라서 입력이 다음과 같으면

(0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (1, 1), (1, 2), (2, 2),(2, 1), (2, 0).

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• N :=행렬의 행 수
• M :=행렬의 열 개수
• dp :=크기 M의 목록과 -1로 채우기
• 0 ~ N - 1 범위의 i에 대해
  • ndp :=M 크기 목록 및 -1로 채우기
  • ndp2 :=M 크기 목록 및 -1로 채우기
  • 0 ~ M - 1 범위의 j에 대해
    • 행렬[i, j]가 1이 아니고 (i가 0 또는 dp[j]> -1과 같으면)
      • ndp[j] :=dp[j] + 1
      • ndp2[j] :=dp[j] + 1
  • 1 ~ M - 1 범위의 j에 대해
    • 행렬[i, j]가 1이 아니고 ndp[j - 1]> -1이면
      • ndp[j] :=ndp[j] 및 (ndp[j - 1] + 1)의 최대값
  • M - 2 ~ 0 범위의 j에 대해 1 감소, do
    • 행렬[i, j]가 1이 아니고 ndp2[j + 1]> -1이면
      • ndp2[j] :=ndp2[j] 및 (ndp2[j + 1] + 1)의 최대값
      • ndp[j] :=ndp[j] 및 ndp2[j]의 최대값
  • dp :=ndp
• 반환(최대 dp) + 1

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(matrix):
   N = len(matrix)
   M = len(matrix[0])
   dp = [-1 for i in matrix[0]]
   for i in range(N):
      ndp = [-1 for j in matrix[0]]
      ndp2 = [-1 for j in matrix[0]]
      for j in range(M):
         if matrix[i][j] != 1 and (i == 0 or dp[j] > -1):
            ndp[j] = dp[j] + 1
            ndp2[j] = dp[j] + 1

      for j in range(1, M):
         if matrix[i][j] != 1 and ndp[j - 1] > -1:
            ndp[j] = max(ndp[j], ndp[j - 1] + 1)

      for j in range(M - 2, -1, -1):
         if matrix[i][j] != 1 and ndp2[j + 1] > -1:
            ndp2[j] = max(ndp2[j], ndp2[j + 1] + 1)
            ndp[j] = max(ndp[j], ndp2[j])

      dp = ndp
   return max(dp) + 1

matrix = [
[0, 0, 0, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
print(solve(matrix))

입력

[
[0, 0, 0, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]

출력

10