六. Union find 1 Surrounded Regio

Idea: here we use the "flood fill" to solve this problem.

Firstly, all the "O" on the edge are replaced by "M".

Next, the BFS is applied here to find the "O" neighbors and replace all of them by "M". Up to date, all the connected "O" are found as "M" and the remained node "O" are all unconnected node.

Finally, substitute "X" for all remained "O" and then use "O" to take the place of all "M".

class Solution:
    """
    @param: board: board a 2D board containing 'X' and 'O'
    @return: nothing
    """
    def surroundedRegions(self, board):
        # write your code here
        if not board:
            return board
        list = []
        x = len(board) 
        y = len(board[0]) 
        
        if x < 3:
            return board
        # substitute  "M" for all "O" on the edges
        for i in range(0, y):
            if board[0][i] == "O":
                board[0][i] = "M"
                list.append((0,i))
            if board[x-1][i] == "O":
                board[x-1][i] = "M"
                list.append((x-1,i))
                
        for i in range(0, x):
            if board[i][0] == "O":
                board[i][0] = "M"
                list.append((i,0))
            if board[i][y-1] == "O":
                board[i][y-1] = "M"
                list.append((i,y-1))
        
        if not len(list): 
            for i in range(0, x):
                for j in range(0, y):
                    if board[j][i] == "O":
                        board[j][i] = "X"
            return
        # replace all connected  "O" by "M"   
        node = list.pop(0)
        bool = True
        while bool:
            if node[0]+1 < x-1 and 0 < node[0]+1:  
                if board[node[0]+1][node[1]] == "O":
                    board[node[0]+1][node[1]] = "M"
                    list.append((node[0]+1, node[1]))
                    
            if node[1]+1 < y-1 and 0 < node[1]+1:
                if board[node[0]][node[1]+1] == "O":
                    board[node[0]][node[1]+1] = "M"
                    list.append((node[0],node[1]+1))
            
            if node[0]-1 > 0 and node[0]-1 < x-1:
                if board[node[0]-1][node[1]] == "O":
                    board[node[0]-1][node[1]] = "M"
                    list.append((node[0]-1,node[1]))
                
            if node[1]-1 > 0 and node[1]-1 < y-1:
                if board[node[0]][node[1]-1] == "O":
                    board[node[0]][node[1]-1] = "M"
                    list.append((node[0],node[1]-1))
                
            if not len(list):
                bool = False
            else:
                node = list.pop(0)
        #  substitute "X" for all remained "O"  
        #  then use "O" to take the place of all "M"
        for i in range(0, x):
            for j in range(0, y):
                if board[i][j] == "O":
                    board[i][j] = "X"
                if board[i][j] == "M":
                    board[i][j] = "O"
                
        return