capture_surrounded_regions.py

from queue import Queue


def flood_fill(board, i, j):
    n, m = len(board), len(board[0])
    queue = Queue()
    queue.put((i, j))
    board[i][j] = '-'
    while not queue.empty():
        i, j = queue.get()
        for adj_i, adj_j in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
            if 0 <= adj_i < n and 0 <= adj_j < m and board[adj_i][adj_j] == 'O':
                queue.put((adj_i, adj_j))
                board[adj_i][adj_j] = '-'


def capture_surrounded(board):
    n, m = len(board), len(board[0])
    for j in range(m):
        if board[0][j] == 'O':
            flood_fill(board, 0, j)
        if board[n-1][j] == 'O':
            flood_fill(board, n-1, j)
    for i in range(1, n-1):
        if board[i][0] == 'O':
            flood_fill(board, i, 0)
        if board[i][m-1] == 'O':
            flood_fill(board, i, m-1)
    for i in range(n):
        for j in range(m):
            if board[i][j] == '-':
                board[i][j] = 'O'
            else:
                board[i][j] = 'X'
                

board = [
    ['X', 'X', 'X', 'X'],
    ['X', 'O', 'O', 'X'],
    ['X', 'X', 'O', 'X'],
    ['X', 'O', 'X', 'X']
]
capture_surrounded(board)
print(*board, sep='\n')

# Output:
# ['X', 'X', 'X', 'X']
# ['X', 'X', 'X', 'X']
# ['X', 'X', 'X', 'X']
# ['X', 'O', 'X', 'X']