Python에서 미로 행렬을 탈출하기 위한 최소 이동 횟수

0이 빈 셀을 나타내고 1이 벽인 이진 행렬이 있다고 가정합니다. 왼쪽 위 모서리(0, 0)에서 시작하면 오른쪽 아래 모서리(R-1, C-1)에 도달하는 데 필요한 최소 셀 수를 찾아야 합니다. 여기서 R은 행 수이고 C는 숫자입니다. 열의. 답을 찾을 수 없으면 -1을 반환합니다.

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

다음과 같은 경로를 선택할 수 있기 때문에 출력은 8이 됩니다. -

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

• R :=행 수
• C :=열 수
• q :=빈 목록, 처음에 행렬[0, 0]이 0이면 (0, 0, 1) 삽입
• 행렬[0, 0] :=1
• q의 각 삼중항(r, c, d)에 대해 다음을 수행합니다.
  • (r, c)가 (R - 1, C - 1)과 같으면
    • 반환 d
  • 각 x, y에 대해 [(r + 1, c) ,(r - 1, c) ,(r, c + 1) ,(r, c - 1) ], do
    • 0 <=x
    • 행렬[x, y] :=1
    • q 끝에 삼중항(x, y, d + 1) 삽입

예

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

def solve(matrix):
   R, C = len(matrix), len(matrix[0])
   q = [(0, 0, 1)] if not matrix[0][0] else []
   matrix[0][0] = 1
   for r, c, d in q:
      if (r, c) == (R - 1, C - 1):
         return d
      for x, y in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
         if 0 <= x < R and 0 <= y < C and matrix[x][y] == 0:
            matrix[x][y] = 1
            q.append((x, y, d + 1))
   return -1

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

입력

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

출력

8