力扣：130. 被围绕的区域（Python3）

题目：

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

来源：力扣（LeetCode）
链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

示例：

示例 1：

输入：board = [["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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [["X"]]
输出：[["X"]]

解法：

首先分析题目，最后保留的O只可能从边界蔓延得到，所以遍历矩阵四周。

接着把遇到的每个O的坐标入队。

然后BFS，创建和矩阵相同大小的矩阵matrix，用来记录最后的O。取出队头坐标，记录，判断上下左右是否为O且尚未记录，如果是就入队，直到队空。

最后根据matrix修改矩阵。

代码：

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        row = len(board) - 1
        col = len(board[0]) - 1
        rh = 1
        ch = 0
        flag = 1
        r = c = 0
        matrix = [[0] * (col + 1) for _ in range(row + 1)]
        q = []
        for _ in range(max(1, 2 * (row + 1 + col + 1) - 4)):
            if flag == 1:
                if board[r][c] == 'O' and matrix[r][c] == 0:
                    q.append((r, c))
                if c == col:
                    r += 1
                    flag = 2
                else:
                    c += 1
            elif flag == 2:
                if board[r][c] == 'O' and matrix[r][c] == 0:
                    q.append((r, c))
                if r == row:
                    c -= 1
                    flag = 3
                else:
                    r += 1
            elif flag == 3:
                if board[r][c] == 'O' and matrix[r][c] == 0:
                    q.append((r, c))
                if c == ch:
                    r -= 1
                    flag = 4
                else:
                    c -= 1
            else:
                if board[r][c] == 'O' and matrix[r][c] == 0:
                    q.append((r, c))
                if r != rh:
                    r -= 1
        while q:
            cur = q.pop(0)
            matrix[cur[0]][cur[1]] = 1
            try:
                if board[cur[0] - 1][cur[1]] == 'O' and matrix[cur[0] - 1][cur[1]] == 0:
                    q.append((cur[0] - 1, cur[1]))
            except IndexError:
                pass
            try:
                if board[cur[0]][cur[1] + 1] == 'O' and matrix[cur[0]][cur[1] + 1] == 0:
                    q.append((cur[0], cur[1] + 1))
            except IndexError:
                pass
            try:
                if board[cur[0] + 1][cur[1]] == 'O' and matrix[cur[0] + 1][cur[1]] == 0:
                    q.append((cur[0] + 1, cur[1]))
            except IndexError:
                pass
            try:
                if board[cur[0]][cur[1] - 1] == 'O' and matrix[cur[0]][cur[1] - 1] == 0:
                    q.append((cur[0], cur[1] - 1))
            except IndexError:
                pass
        for r in range(row + 1):
            for c in range(col + 1):
                if board[r][c] == 'O' and matrix[r][c] == 0:
                    board[r][c] = 'X'