Surrounded Regions

Intuition

Solution

from collections import deque


class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board:
            return

        m = len(board)
        n = len(board[0])
        queue = deque([])
        for i in range(m):
            if board[i][0] == 'O':
                queue.append([i, 0])
                board[i][0] = 'o'
            if board[i][n - 1] == 'O':
                queue.append([i, n - 1])
                board[i][n - 1] = 'o'
        for j in range(n):
            if board[0][j] == 'O':
                queue.append([0, j])
                board[0][j] = 'o'
            if board[m - 1][j] == 'O':
                queue.append([m - 1, j])
                board[m - 1][j] = 'o'
        while queue:
            i, j = queue.popleft()
            for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                if not (0 <= x < m and 0 <= y < n):
                    continue
                if board[x][y] == 'O':
                    board[x][y] = 'o'
                    queue.append([x, y])
        for i in range(m):
            for j in range(n):
                board[i][j] = 'O' if board[i][j] == 'o' else 'X'