Python에서 오른쪽 하단에 도달하는 데 필요한 최소 셀 수를 찾는 프로그램

0이 빈 공간이고 1이 벽인 미로를 나타내는 2D 그리드가 있다고 가정합니다. grid[0, 0]에서 시작합니다. 그리드의 오른쪽 하단 모서리에 도달하는 데 필요한 최소 사각형 수를 찾아야 합니다. 도달할 수 없으면 -1을 반환합니다.

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

그러면 출력은 5가 됩니다.

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

• R :=그리드의 행 개수, C :=그리드의 열 개수

• q :=[0, 0, 1] A[0, 0]이 1이면 새 목록

• A[0, 0] :=1

• q의 각 (r, c, d)에 대해 수행

  • (r, c)가 (R − 1, C − 1)과 같으면

    • 리턴 d

  • 
    

    • [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1) ]의 각 (x, y)에 대해

      • 0~R 범위의 x와 0~C 범위의 y 및 A[x, y]가 0과 같으면

        • A[x, y] :=1

        • q의 끝에 (x, y, d + 1) 삽입

• 반환 -1

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

예시

class Solution:
   def solve(self, A):
      R, C = len(A), len(A[0])
      q = [(0, 0, 1)] if not A[0][0] else []
      A[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 A[x][y] == 0:
               A[x][y] = 1
               q.append((x, y, d + 1))
      return −1
ob = Solution()
grid = [
   [0, 0, 0],
   [1, 0, 0],
   [1, 0, 0]
]
print(ob.solve(grid))

입력

grid = [ [0, 0, 0], [1, 0, 0], [1, 0, 0] ]

출력

5