Surrounded Regions (ยึดครองพื้นที่) ใน Python

ใน board 2D ของ 'X' และ 'O' ให้เปลี่ยน 'O' ที่ถูกล้อมรอบโดย 'X' ทั้ง 4 ทิศทาง เป็น 'X' (ยกเว้น 'O' ที่สัมผัสขอบ)

ตัวอย่าง

Input:
X X X X
X O O X
X X O X
X O X X

Output:
X X X X
X X X X
X X X X
X O X X  # O ล่างสุดไม่ถูกล้อม เพราะสัมผัสขอบ

อัลกอริทึม: Flood Fill จากขอบ

1. DFS/BFS จาก 'O' ที่อยู่ขอบ 4 ด้าน → mark เป็น '1' (safe)
2. วนทั้ง board: 'O' → 'X' (captured), '1' → 'O' (restore)

โค้ด

class Solution:
    def solve(self, board):
        if not board:
            return
        
        rows, cols = len(board), len(board[0])
        
        def dfs(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != 'O':
                return
            board[r][c] = '1'  # mark safe
            dfs(r+1, c)
            dfs(r-1, c)
            dfs(r, c+1)
            dfs(r, c-1)
        
        # 1. Mark border-connected 'O's
        for r in range(rows):
            if board[r][0] == 'O': dfs(r, 0)
            if board[r][cols-1] == 'O': dfs(r, cols-1)
        for c in range(cols):
            if board[0][c] == 'O': dfs(0, c)
            if board[rows-1][c] == 'O': dfs(rows-1, c)
        
        # 2. Flip
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == '1':
                    board[r][c] = 'O'

# ทดสอบ
board = [
    ["X","X","X","X"],
    ["X","O","O","X"],
    ["X","X","O","X"],
    ["X","O","X","X"]
]
sol = Solution()
sol.solve(board)
for row in board:
    print(row)

ผลลัพธ์

['X', 'X', 'X', 'X']
['X', 'X', 'X', 'X']
['X', 'X', 'X', 'X']
['X', 'O', 'X', 'X']

สรุป

Reverse thinking: หา 'O' ที่ปลอดภัย (เชื่อมขอบ) ก่อน แล้วค่อย flip ที่เหลือ