จับพื้นที่ถูกล้อมรอบ (Surrounded Regions) ใน Python

โจทย์: กำหนดบอร์ด 2D ที่มี 'X' และ 'O' จับพื้นที่ 'O' ที่ถูกล้อมรอบโดย 'X' ทั้ง 4 ด้าน โดยเปลี่ยน 'O' ในพื้นที่นั้นเป็น 'X'

ตัวอย่าง

Input:

X X X X
X O O X
X X O X
X O X X

X X X X
X X X X
X X X X
X O X X

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

1. DFS/BFS จาก 'O' บนขอบ 4 ด้าน → มาร์กเป็น '1' (ปลอดภัย)
2. สแกนทั้งบอร์ด: 'O' → 'X' (ถูกล้อมรอบ), '1' → 'O' (คืนค่า)

ตัวอย่างโค้ด Python

class Solution(object):
    def solve(self, board):
        if not board:
            return board
        
        rows, cols = len(board), len(board[0])
        
        def dfs(i, j):
            if i < 0 or i >= rows or j < 0 or j >= cols or board[i][j] != 'O':
                return
            board[i][j] = '1'  # มาร์กปลอดภัย
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
        
        # 1. Flood fill จากขอบ
        for i in range(rows):
            if board[i][0] == 'O': dfs(i, 0)
            if board[i][cols-1] == 'O': dfs(i, cols-1)
        
        for j in range(cols):
            if board[0][j] == 'O': dfs(0, j)
            if board[rows-1][j] == 'O': dfs(rows-1, j)
        
        # 2. อัปเดตบอร์ด
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == '1':
                    board[i][j] = 'O'
        
        return board

# ทดสอบ
ob = Solution()
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
print(ob.solve(board))
# Output: [['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','O','X','X']]

ตัวอย่าง Input/Output

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']]

ความซับซ้อน: Time O(m×n), Space O(m×n) สำหรับ recursion stack