ข้อ 48 · LC994 Rotting Oranges (ส้มเน่า) 🟡

โจทย์ (LC994): กำหนด grid ขนาด m x n ที่แต่ละช่องมีค่าได้สามแบบ คือ 0 (ช่องว่าง), 1 (ส้มสด), หรือ 2 (ส้มเน่า) ทุก ๆ หนึ่งนาที ส้มสดที่อยู่ติดกัน 4 ทิศ (บน ล่าง ซ้าย ขวา) กับส้มเน่าจะเน่าตามไปด้วย ให้ return จำนวนนาทีน้อยที่สุดที่ต้องใช้จนไม่มีส้มสดเหลืออยู่เลย ถ้าเป็นไปไม่ได้ (มีส้มสดที่ไม่มีวันเน่า) ให้ return -1

แนวทาง — ต้องใช้อะไร & คิดยังไง

ใช้ multi-source BFS จุดที่ทำให้ข้อนี้ต่างจากข้อก่อนคือมันมีจุดเริ่ม หลายจุดพร้อมกัน (ส้มเน่าทุกลูกลามในเวลาเดียวกัน) เราจึงไม่ได้เริ่มจากจุดเดียว แต่ push (ใส่) ส้มเน่าทุกลูกเข้า queue (คิว) ตั้งแต่ต้น แล้ว BFS แผ่ออกพร้อมกันหมด คลื่นการเน่าจึงขยายทีละวงพอดีกับเวลาจริง

การนับนาทีต้องประมวลผล ทีละชั้น (level) ใช้ for _ in range(len(queue)) ก่อน pop (ดึง) ของ เพื่อจัดการเฉพาะส้มที่เน่าอยู่ ณ ต้นนาทีนี้ให้ครบก่อน ค่อยขึ้นนาทีใหม่ และใช้ตัวแปร fresh count (นับ) ส้มสดที่เหลือ ทุกครั้งที่ทำให้ลูกหนึ่งเน่าก็ลด fresh ลง สุดท้ายถ้า fresh ยังเหลือแปลว่าเน่าไม่ทั่ว

1. iterate (วน) ทั้ง grid push ตำแหน่งส้มเน่าทุกลูกเข้า queue และ count จำนวนส้มสด (fresh)
2. ถ้า fresh เป็น 0 ตั้งแต่แรก return 0 ทันที (ไม่ต้องรอเวลา)
3. iterate while queue และ fresh > 0 บวก minutes หนึ่งในแต่ละรอบ
4. pop ส้มเน่าทั้ง level นี้ออก (for _ in range(len(queue))) ทำให้ neighbor (เพื่อนบ้าน) ที่เป็นส้มสดเน่าตาม
5. แต่ละลูกที่เน่าใหม่ ตั้งเป็น 2 ลด fresh แล้ว append (ต่อท้าย) เข้า queue เป็นแหล่งเน่าของนาทีถัดไป
6. จบ loop ถ้า fresh เป็น 0 return minutes ไม่งั้น return -1

ไล่ทีละสเต็ป

รันบน grid = [[2,1,1],[1,1,0],[0,1,1]] (เริ่มมีส้มเน่าที่ (0,0), fresh = 6)

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    # หาตำแหน่งส้มเน่าทั้งหมด (จุดเริ่มหลายจุด) และนับส้มสด
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    if fresh == 0:
        return 0                     # ไม่มีส้มสดตั้งแต่แรก ใช้ 0 นาที

    minutes = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue and fresh > 0:
        minutes += 1                 # ผ่านไปอีกหนึ่งนาที
        for _ in range(len(queue)):  # แผ่ทั้งชั้น (ส้มเน่า ณ นาทีนี้) พร้อมกัน
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2         # ส้มสดเน่าตาม
                    fresh -= 1
                    queue.append((nr, nc))   # กลายเป็นแหล่งเน่าในนาทีถัดไป

    return minutes if fresh == 0 else -1     # ถ้ายังเหลือส้มสด แปลว่าเน่าไม่ถึง

print(oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))  # 4
print(oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]))  # -1
print(oranges_rotting([[0, 2]]))                           # 0

4
-1
0