파이썬에서 모든 나무를 태우는 데 걸리는 일수를 찾는 프로그램

세 가지 유형의 세포가 있는 숲을 나타내는 2D 행렬이 있다고 가정합니다. 0 빈 세포 1 나무 세포 2 불 세포에 있는 나무 매일 인접한 나무가 있을 때 나무에 불이 붙습니다. 대각선) 나무가 불타고 있습니다. 우리는 모든 나무에 불이 붙는 데 걸리는 일수를 찾아야 합니다. 가능하지 않으면 -1을 반환합니다.

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

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

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

• ans :=0
• twos :=새 목록
• 행렬의 행 수까지 범위 0에 있는 i에 대해 다음을 수행합니다.
  • 행렬의 열 개수까지 범위 0에 있는 j의 경우 수행
    • 행렬[i,j]가 2와 같으면
      • 둘 끝에 쌍(i, j) 삽입
    • 2가 비어 있지 않은 동안 do
      • temp :=새 목록
      • 각 쌍(i, j)에 대해 2개로
        • [(i + 1, j) ,(i, j + 1) ,(i - 1, j) ,(i, j - 1) ]의 각 쌍(x, y)에 대해, do
          • x와 y가 행렬의 범위에 있고 행렬[x, y]가 1이면
            • 온도 끝에 쌍(x, y) 삽입
      • 각 쌍(i, j)에 대해 temp, do
        • 행렬[i, j] :=2
      • 둘 :=임시
      • ans :=ans + (2가 비어 있지 않으면 1, 그렇지 않으면 0)
    • ones =행렬의 1 개수 계산
    • 1이 0인 경우 반환, 그렇지 않으면 -1

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

예시

class Solution:
   def solve(self, matrix):
      ans = 0
      twos = []
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            if matrix[i][j] == 2:
               twos.append((i, j))
      while twos:
         temp = []
         for i, j in twos:
            for x, y in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
               if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and matrix[x][y] == 1:
                  temp.append((x, y))
         for i, j in temp:
            matrix[i][j] = 2
         twos = temp
         ans += 1 if twos else 0

      ones = sum(int(matrix[i][j] == 1) for i in range(len(matrix)) for j in range(len(matrix[0])))
      return ans if ones == 0 else -1

ob = Solution()
matrix = [
   [1, 2, 1],
   [1, 0, 1],
   [1, 1, 1]
]
print(ob.solve(matrix))

입력

matrix = [  
[1, 2, 1],  
[1, 0, 1],  
[1, 1, 1] ]

출력

4