โปรแกรมหาจำนวนวันที่ต้องเผาต้นไม้ทั้งหมดใน python

สมมติว่าเรามีเมทริกซ์ 2 มิติ แทนผืนป่าที่มีเซลล์สามประเภท:0 เซลล์ว่าง 1 เซลล์ต้นไม้ 2 ต้นไม้บนเซลล์ไฟ ทุกวัน ต้นไม้จะลุกเป็นไฟเมื่อมีเซลล์ที่อยู่ติดกัน (บน ล่าง ซ้าย ขวา ไม่ใช่ แนวทแยง) ต้นไม้ติดไฟ เราต้องหาจำนวนวันที่ต้นไม้ทุกต้นจะลุกเป็นไฟได้ หากไม่สามารถคืนได้ -1.

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ตอบ :=0
• twos :=รายการใหม่
• สำหรับ i ในช่วง 0 ถึงจำนวนแถวของเมทริกซ์ ทำ
  • สำหรับ j ในช่วง 0 ถึงจำนวนคอลัมน์ของเมทริกซ์ ให้ทำ
    • ถ้า matrix[i, j] เหมือนกับ 2 แล้ว
      • ใส่คู่ (i, j) ที่ส่วนท้ายของสอง
    • ในขณะที่ twos ไม่ว่างเปล่า ทำ
      • temp :=รายการใหม่
      • สำหรับแต่ละคู่ (i, j) ในสอง ทำ
        • สำหรับแต่ละคู่ (x, y) ใน [(i + 1, j) ,(i, j + 1) ,(i - 1, j) ,(i, j - 1) ] ทำ
          • ถ้า x และ y อยู่ในช่วงของเมทริกซ์และเมทริกซ์[x, y] คือ 1 ดังนั้น
            • ใส่คู่ (x, y) ที่จุดสิ้นสุดของอุณหภูมิ
      • สำหรับแต่ละคู่ (i, j) ในอุณหภูมิ ให้ทำ
        • เมทริกซ์[i, j] :=2
      • สอง :=อุณหภูมิ
      • ans :=ans + (1 ถ้า twos ไม่ว่างเปล่า มิฉะนั้น 0)
    • ones =นับจำนวน 1s ในเมทริกซ์
    • ส่งคืน ans ถ้าอันหนึ่งเป็น 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