Python에서 목표에 도달하는 최단 경로를 찾는 프로그램

셀에 'X', 'O', '*' 및 '#'과 같은 다양한 기호가 포함되고 기호에 다양한 의미가 있는 그리드가 있다고 가정합니다.

• '#'는 도달하려는 목표 셀입니다.
• 'O'는 목표 셀로 이동할 수 있는 자유 셀입니다.
• '*'는 셀에서 우리의 위치입니다.
• 'X'는 우리가 이동할 수 없는 차단된 세포입니다.

그리드의 현재 위치에서 목표 셀에 도달하는 데 필요한 이동 수를 찾아야 합니다. 목표에 도달할 수 없으면 -1을 반환합니다. 그리드는 프로그램에 대한 입력으로 제공됩니다.

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

그러면 출력은 2

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

• m :=그리드의 행 수
• n :=그리드의 열 개수
• 0~m 범위의 i에 대해
  • 0에서 n 사이의 j에 대해 다음을 수행합니다.
    • 그리드[i, j]가 "*"와 같으면
      • 루프에서 나오다
    • 그렇지 않으면
      • 다음 반복으로 이동
    • 루프에서 나오다
• ans :=0
• queue :=정수 쌍(i, j)을 포함하는 새 목록
• 그리드[i, j] :="X"
• 대기열이 비어 있지 않은 동안 수행
  • ans :=ans + 1
  • newq :=새 목록
  • 대기열의 각 i, j에 대해 수행
    • 각 ii, jj in(i-1, j) ,(i, j-1) ,(i, j+1) ,(i+1, j), do
      • 0 <=ii
      • 그리드[ii, jj]가 "#"과 같으면
        • 반환
      • newq 끝에 ii, jj 삽입
      • 그리드[ii, jj] :="X"
• 대기열:=newq

예시

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

def solve(grid):
   m, n = len(grid), len(grid[0])
   for i in range(m):
      for j in range(n):
         if grid[i][j] == "*": break
      else: continue
      break
   ans = 0
   queue = [(i, j)]
   grid[i][j] = "X"
   while queue:
      ans += 1
      newq = []
      for i, j in queue:
         for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
            if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
               if grid[ii][jj] == "#": return ans
               newq.append((ii, jj))
               grid[ii][jj] = "X"
      queue = newq
   return -1

print(solve([['X', 'X', 'O', 'X'],['X', 'X', '*', 'X'],['X', '#',
'O', 'X'],['X', 'X', 'X', 'X']]))

입력

[['X', 'X', 'O', 'X'],
['X', 'X', '*', 'X'],
['X', '#', 'O', 'X'],
['X', 'X', 'X', 'X']]

출력

2