Surrounded Regions – Python 3 (Week 12 – 10)

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        if not board or len(board) == 0 or len(board[0]) == 0:
                return
            
        n = len(board)
        m = len(board[0])
        
        
        
        for i in range(n):
            self.bfs(board, i, 0)
            self.bfs(board, i, m - 1)
            
        for j in range(m):
            self.bfs(board, 0, j)
            self.bfs(board, n - 1, j) 
        
        for i in range(n):
            for j in range(m):
                if board[i][j] == 'W':
                    board[i][j] = 'O'
                else:
                    board[i][j] = 'X'  
        
        
    def bfs(self, board, x, y):
        if board[x][y] != 'O':
            return
        
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        
        qx = []
        qy = []
        qx.append(x)
        qy.append(y)
        
        board[x][y] = 'W'
        
        while qx:
            cx = qx.pop()
            cy = qy.pop()
            
            for i in range(4):
                nx = cx + dx[i]
                ny = cy + dy[i]
                if nx >= 0 and nx < len(board) and ny >= 0 and ny < len(board[0]) and board[nx][ny] == 'O':
                    board[nx][ny] = 'W'
                    qx.append(nx)
                    qy.append(ny)
                    

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

        n, m = len(board), len(board[0])
        q = [ij for k in range(max(n,m)) for ij in ((0, k), (n-1, k), (k, 0), (k, m-1))]
        while q:
            i, j = q.pop()
            if 0 <= i < n and 0 <= j < m and board[i][j] == 'O':
                board[i][j] = 'W'
                q += (i, j-1), (i, j+1), (i-1, j), (i+1, j)

        board[:] = [['XO'[c == 'W'] for c in row] for row in board]