โปรแกรมนับกำแพงขั้นต่ำแบ่งมุมซ้ายบน-ขวาล่างใน Python

คำอธิบายโจทย์

เมทริกซ์ไบนารี 0=ว่าง 1=กำแพง หาจำนวนเซลล์น้อยที่สุดที่ต้องเปลี่ยนเป็นกำแพง เพื่อไม่ให้มีทางจาก (0,0) ไป (R-1,C-1) เดิน 4 ทิศทาง ไม่ให้วางกำแพงบนมุมเริ่ม/ปลาย

ตัวอย่าง

เมทริกซ์ 4x4 → เอาต์พุต: 2 (ต้องเพิ่มกำแพง 2 เซลล์)

วิธีแก้ปัญหา

Articulation Points (Cut Vertices) + DFS + BFS:

1. หา Articulation Points บนกราฟของเซลล์ว่าง (0) เริ่มจาก (0,0)
2. Articulation point = เซลล์ที่ถ้าลบออกจะทำให้กราฟขาดการเชื่อมต่อ
3. ถ้า target ไม่ reachable จาก source ตั้งแต่แรก → คืน 0
4. ลบ articulation points ทั้งหมด (เปลี่ยนเป็นกำแพง)
5. BFS เช็คว่า target ยัง reachable หรือไม่ ถ้า reachable → ต้องเพิ่มอีก 2, ไม่ reachable → 1

โค้ด Python

from collections import deque

class Solution:
    def solve(self, matrix):
        R = len(matrix)
        C = len(matrix[0])
        
        def get_neighbors(i, j):
            for ii, jj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                if 0 <= ii < R and 0 <= jj < C and matrix[ii][jj] == 0:
                    yield ii, jj
        
        visited = set()
        tin = {}
        low = {}
        timer = 0
        bridge_pts = set()
        par = {}
        src = (0, 0)
        tgt = (R - 1, C - 1)
        
        def dfs(v, parent):
            nonlocal timer
            visited.add(v)
            par[v] = parent
            tin[v] = timer
            low[v] = timer
            timer += 1
            children = 0
            for to in get_neighbors(*v):
                if to == parent:
                    continue
                if to in visited:
                    low[v] = min(low[v], tin[to])
                else:
                    dfs(to, v)
                    low[v] = min(low[v], low[to])
                    if low[to] >= tin[v] and parent is not None:
                        bridge_pts.add(v)
                    children += 1
            if parent is None and children > 1:
                bridge_pts.add(v)
        
        def bfs(root):
            Q = deque([root])
            visited = set([root])
            while Q:
                v = Q.pop()
                if v == tgt:
                    return True
                for w in get_neighbors(*v):
                    if w not in visited:
                        visited.add(w)
                        Q.appendleft(w)
            return False
        
        dfs(src, None)
        if tgt not in par:
            return 0
        for i, j in bridge_pts:
            matrix[i][j] = 1
        if bfs(src):
            return 2
        return 1

ob = Solution()
matrix = [
    [0, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
]
print(ob.solve(matrix))

อินพุต

[[0,0,0,0],[0,1,0,0],[0,1,1,0],[0,0,0,0]]

เอาต์พุต

2