사람을 확인하는 프로그램은 Python에서 화재를 피하는지 여부를 왼쪽 위 또는 오른쪽 아래 셀에 도달할 수 있습니다.

아래와 같이 서로 다른 값이 거의 없는 2D 행렬이 있다고 가정합니다. -

• 빈 셀의 경우 0

• 1인용

• 2 불

• 벽에 3개

이제 사람이 한 명뿐이고 각 턴에 불이 네 방향(위, 아래, 왼쪽, 오른쪽)으로 확장되지만 벽을 통해 확장할 수 없다고 가정합니다. 사람이 왼쪽 위 모서리나 오른쪽 아래 모서리 또는 행렬로 이동할 수 있는지 확인해야 합니다. 우리는 매 턴마다 사람이 먼저 움직이고 그 다음에 불이 확장된다는 것을 명심해야 합니다. 사람이 화재와 같은 시간에 목표 세포 중 하나에 도달하면 안전합니다. 따라서 사람이 감방에 갔다가 불이 같은 방으로 번져도 그 사람은 여전히 ​​살아남습니다.

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

사람이 왼쪽 상단으로 이동할 수 있으므로 출력은 True가 됩니다.

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

• R :=A의 행 개수, C :=A의 열 개수

• bfs() 함수를 정의합니다. 대기열이 필요합니다.

• dist :=큐의 노드로 키를 포함하고 모든 값이 0인 맵

• 대기열이 비어 있지 않은 동안 수행

  • node :=큐의 왼쪽 항목, 그 다음 왼쪽 항목 삭제

  • 노드의 각 이웃 nei에 대해 수행

    • nei가 dist에 없으면

      • dist[nei] :=dist[노드] + 1

      • 대기열 끝에 nei 삽입

• 반환 거리

• 주요 방법에서 다음을 수행하십시오 -

• fire_que :=이중 종료 대기열

• person_que :=이중 종료 대기열

• 각 행 인덱스 r 및 행 A에 대해 수행

  • 행의 각 열 인덱스 c 및 값 v에 대해 수행

    • v가 1과 같으면

      • person_que의 끝에 쌍(r, c) 삽입

    • 그렇지 않으면 v가 2와 같을 때

      • fire_que의 끝에 쌍(r, c) 삽입

      • dist_fire :=bfs(fire_que)

• dist_person :=bfs(person_que)

• (0, 0), (R − 1, C − 1)의 각 자리에 대해 수행

  • if (dist_fire[place] if not exist then INF)>=(dist_person[place] if not exist then, 2 * INF), then

    • 참을 반환

• 거짓을 반환

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

예시

from collections import deque
class Solution:
   def solve(self, A):
      INF = int(1e9)
      R, C = len(A), len(A[0])
      def get_nei(r, c):
         for nr, nc in [[r − 1, c], [r, c − 1], [r + 1, c], [r, c + 1]]:
            if 0 <= nr < R and 0 <= nc < C and A[nr][nc] != 3:
               yield nr, nc
         def bfs(queue):
            dist = {node: 0 for node in queue}
            while queue:
               node = queue.popleft()
               for nei in get_nei(*node):
                  if nei not in dist:
                     dist[nei] = dist[node] + 1
                     queue.append(nei)
            return dist
         fire_que = deque()
         person_que = deque()
         for r, row in enumerate(A):
            for c, v in enumerate(row):
               if v == 1:
                  person_que.append((r, c))
               elif v == 2:
                  fire_que.append((r, c))
         dist_fire = bfs(fire_que)
         dist_person = bfs(person_que)
         for place in ((0, 0), (R− 1, C− 1)):
            if dist_fire.get(place, INF) >= dist_person.get(place, 2 * INF):
               return True
         return False
ob = Solution()
matrix = [
   [0, 0, 0],
   [0, 0, 1],
   [0, 0, 2]
]
print(ob.solve(matrix))

입력

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

출력

True