สมมติว่าเมทริกซ์ 2D แทนป่า: 0=ว่าง, 1=ต้นไม้, 2=ไฟ ทุกวัน ต้นไม้จะไหม้ถ้ามีเพื่อนบ้าน (บนล่างซ้ายขวา) อยู่ในสถานะไฟ หาจำนวนวันที่ใช้จนต้นไม้ทั้งหมดไหม้ ถ้าไม่ได้คืน -1
เช่น เมทริกซ์ [[1,2,1],[1,0,1],[1,1,1]] ให้ผลลัพธ์ 4
ขั้นตอนการแก้ปัญหา
- เก็บตำแหน่งไฟเริ่มต้นใน
twos - ทำ BFS ทุกวัน: ขยายไฟไปเพื่อนบ้านที่เป็นต้นไม้ (1)
- นับจำนวนวันจนไม่มีการขยายใหม่
- ตรวจสอบว่าเหลือต้นไม้ (1) หรือไม่ ถ้ามีคืน -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
อินพุต
matrix = [[1,2,1],[1,0,1],[1,1,1]]
เอาต์พุต
4
