Chương trình tìm số ngày cần để đốt hết cây trong python

Giả sử chúng ta có một ma trận 2D đại diện cho một khu rừng trong đó có ba loại ô:0 ô trống 1 ô cây 2 cây trên ô lửa Mỗi ngày, một cây bắt lửa khi có một ô liền kề (trên, xuống, trái, phải, không đường chéo) cây đang cháy. Chúng ta phải tìm số ngày để mỗi cây cháy. Nếu không được, hãy trả về -1.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 4,

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=0
• twos:=một danh sách mới
• đối với tôi trong phạm vi 0 đến số hàng của ma trận, hãy thực hiện
  • đối với j trong phạm vi 0 đến số cột của ma trận, thực hiện
    • nếu ma trận [i, j] giống 2, thì
      • chèn cặp (i, j) vào cuối hai phần
    • trong khi twos không trống, hãy thực hiện
      • temp:=một danh sách mới
      • đối với mỗi cặp (i, j) trong hai cặp, thực hiện
        • cho mỗi cặp (x, y) trong [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)], thực hiện
          • nếu x và y nằm trong phạm vi của ma trận và ma trận [x, y] là 1 thì
            • chèn cặp (x, y) vào cuối tạm thời
      • đối với mỗi cặp (i, j) trong tạm thời, thực hiện
        • ma trận [i, j]:=2
      • twos:=temp
      • ans:=ans + (1 nếu twos không trống, nếu không 0)
    • ones =đếm số lượng 1 trong ma trận
    • trả về ans nếu những cái là 0, nếu không thì -1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

4