Solutions

# Mark 'O' on the borders and all 'O' connected to them as "visited" (e.g. '#'), then mark all remaining 'O' as 'X', and restore '#' to 'O'. DFS, BFS, or Union-Find.
# graphs

# DFS - O(n*m) time, O(n*m) space
def solve(board: list[list[str]]) -> None:
    # Mark as "visited" all 'O' reachable from 'O' on the borders
    for r in [0, len(board)-1]:
        for c in range(len(board[0])):
            if board[r][c] == 'O':
                mark_region(r,c, board, '#')
            
    for c in [0, len(board[0])-1]:
        for r in range(len(board)):
            if board[r][c] == 'O':
                mark_region(r,c, board, '#')

    # Mark all remaining 'O' as 'X'
    # and restore '#' to 'O'
    for r in range(len(board)):
        for c in range(len(board[0])):
            if board[r][c] == 'O':
                board[r][c] = 'X'
            elif board[r][c] == '#':
                board[r][c] = 'O'

    
def mark_region(r: int, c: int, board: list[list[str]], marker: str):
    n = len(board)
    m = len(board[0])

    if r >= n or r < 0 or c >= m or c < 0:
        return 
    
    if board[r][c] == 'O':
        board[r][c] = marker
        mark_region(r+1,c,board, marker)
        mark_region(r,c+1,board, marker)
        mark_region(r-1,c,board, marker)
        mark_region(r,c-1,board, marker)


# BFS - O(n*m) time, O(n*m) space
from collections import deque

def solve(board: list[list[str]]) -> None:
    ROWS, COLS = len(board), len(board[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def capture():
        q = deque()
        for r in range(ROWS):
            for c in range(COLS):
                if (r == 0 or r == ROWS - 1 or
                    c == 0 or c == COLS - 1) and board[r][c] == "O":
                    q.append((r, c))
        while q:
            r, c = q.popleft()
            if board[r][c] == "O":
                board[r][c] = "#"
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < ROWS and 0 <= nc < COLS:
                        q.append((nr, nc))

    capture()
    for r in range(ROWS):
        for c in range(COLS):
            if board[r][c] == "O":
                board[r][c] = "X"
            elif board[r][c] == "#":
                board[r][c] = "O"

# Union-Find - O(n*m) time, O(n*m) space
class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] >= self.Size[pv]:
            self.Size[pu] += self.Size[pv]
            self.Parent[pv] = pu
        else:
            self.Size[pv] += self.Size[pu]
            self.Parent[pu] = pv
        return True

    def connected(self, u, v):
        return self.find(u) == self.find(v)

def solve(board: list[list[str]]) -> None:
    ROWS, COLS = len(board), len(board[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    dsu = DSU(ROWS * COLS + 1)

    for r in range(ROWS):
        for c in range(COLS):
            if board[r][c] != "O":
                continue
            if (r == 0 or c == 0 or
                r == (ROWS - 1) or c == (COLS - 1)
            ):
                dsu.union(ROWS * COLS, r * COLS + c)
            else:
                for dx, dy in directions:
                    nr, nc = r + dx, c + dy
                    if board[nr][nc] == "O":
                        dsu.union(r * COLS + c, nr * COLS + nc)

    for r in range(ROWS):
        for c in range(COLS):
            if not dsu.connected(ROWS * COLS, r * COLS + c):
                board[r][c] = "X"