LeetCode130. 被围绕的区域

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
解释:
被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：
X X X X
X X X X
X X X X
X O X X

只需找到边沿的O以及与它相邻的那些O，并标记好，其它的最终都填充为X

class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        m = len(board)
        if m == 0:
            return
        
        n = len(board[0])
        mat = [[0]*n for i in range(m)]
        for i in range(m):
            for j in [0,n-1]:
                self.bfs(board,mat,i,j,m,n)
        for j in range(n):
            for i in [0,m-1]:
                self.bfs(board,mat,i,j,m,n)
        for i in range(m):
            for j in range(n):
                if mat[i][j]==0:
                    board[i][j] = 'X'
        return 
        
    def bfs(self,board,mat,i,j,m,n):
        if 0<=i<m and 0<=j<n and board[i][j] == 'O' and mat[i][j]==0:
            queue = []
            queue.append((i,j))
            mat[i][j] = 1
            while queue:
                u,v = queue.pop(0)
                if 0<=u<m and 0<=v+1<n and board[u][v+1] == 'O' and mat[u][v+1]==0:
                    queue.append((u,v+1))
                    mat[u][v+1] = 1
                if 0<=u<m and 0<=v-1<n and board[u][v-1] == 'O' and mat[u][v-1]==0:
                    queue.append((u,v-1))
                    mat[u][v-1] = 1
                if 0<=u+1<m and 0<=v<n and board[u+1][v] == 'O' and mat[u+1][v]==0:
                    queue.append((u+1,v))
                    mat[u+1][v] = 1
                if 0<=u-1<m and 0<=v<n and board[u-1][v] == 'O' and mat[u-1][v]==0:
                    queue.append((u-1,v))
                    mat[u-1][v] = 1