import collections


class Solution:
    """
    @param: board: board a 2D board containing 'X' and 'O'
    @return: nothing
    """
    # DFS
    def surroundedRegions(self, board):
        # write your code here
        if not board or not board[0]:
            return

        m, n = len(board), len(board[0])

        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    if board[i][j] == 'O': # this line can be removed.
                        self.dfs(board, i, j)

        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'M':
                    board[i][j] = 'O'

    def dfs(self, board, i, j):
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        m, n = len(board), len(board[0])
        if i < 0 or i >= m or j < 0 or j >= n:
            return
        if board[i][j] != 'O':
            return

        board[i][j] = 'M'
        for k in range(4):
            x = i + dirs[k][0]
            y = j + dirs[k][1]
            self.dfs(board, x, y)

    # BFS
    def surroundedRegions2(self, board):
        # write your code here
        if not board or not board[0]:
            return
        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]

        m, n = len(board), len(board[0])
        queue = collections.deque()

        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    if board[i][j] == 'O':
                        queue.append((i, j))
                        board[i][j] = 'M'
                        while queue:
                            (x0, y0) = queue.popleft()
                            for k in range(4):
                                x = x0 + dirs[k][0]
                                y = y0 + dirs[k][1]
                                if x < 0 or x >= m or y < 0 or y >= n:
                                    continue
                                if board[x][y] != 'O':
                                    continue
                                queue.append((x, y))
                                board[x][y] = 'M'

        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'M':
                    board[i][j] = 'O'

if __name__ == "__main__":
    sol = Solution()
    board = [['X','X','X','X','X'],['X','X','X','X','X'],['X','X','O','O','X'],['X','X','O','X','X'],
             ['X','X','O','X','X']]
    sol.surroundedRegions2(board)
    print('aaa')