130. 被围绕的区域

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘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’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的解答，程序说明已注释：

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

        h = len(board)
        w = len(board[0])

        if h == 1 or w == 1:
            return board

        # DFS寻找所有边界连通的 O, 使之为 -
        def dfs_flip(y,x, board):
            if board[y][x] != "O":
                return 0
            if board[y][x] == "O":
                board[y][x] = "-"
            if y+1 < h and board[y+1][x] == "O":
                dfs_flip(y+1,x,board)
            if y-1 >= 0 and board[y-1][x] == "O":
                dfs_flip(y-1,x,board)
            if x+1 < w and board[y][x+1] == "O":
                dfs_flip(y,x+1,board)
            if x-1 >= 0 and board[y][x-1] == "O":
                dfs_flip(y,x-1,board)

        # 从边界开始进行DFS
        for i in range(0,h):
            if board[i][0] == "O":
                dfs_flip(i, 0, board)
            if board[i][w-1] == "O":
                dfs_flip(i, w-1, board)
        for j in range(0,w):
            if board[0][j] == "O":
                dfs_flip(0, j, board)
            if board[h-1][j] == "O":
                dfs_flip(h-1,j,board)

        # 所有不与边界连通的 O 区域变成 X，所有 - 变成 O
        for y in range(0, len(board)):
            row = board[y]
            for x in range(0, len(board[0])):
                item = row[x]
                if item == 'O':
                    board[y][x] = 'X'
                if item == '-':
                    board[y][x] = 'O'