Chương trình tính số ngày để đốt cháy hết cây trong rừng bằng Python

Cho ma trận 2D đại diện rừng: 0 (ô trống), 1 (cây), 2 (cây đang cháy). Mỗi ngày, cây bị cháy nếu có cây cháy liền kề (4 hướng). Tìm số ngày để tất cả cây đều cháy. Nếu không thể trả về -1.

Ví dụ: ma trận 3x3 cho ra kết quả 4.

Giải thuật

• Thu thập tất cả ô cháy ban đầu vào danh sách twos.
• Lặp BFS theo ngày:
  • Với mỗi ô cháy, lan sang 4 ô liền kề là cây (1) → thêm vào temp.
  • Cập nhật các ô trong temp thành 2.
  • twos = temp, tăng ngày nếu temp không rỗng.
• Sau BFS, đếm số ô còn giá trị 1. Nếu bằng 0 trả về số ngày, ngược lại -1.

Ví dụ minh họa

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