每日一道leetcode（python）130. 被围绕的区域

每日一道leetcode（python）130. 被围绕的区域

2021-09-08

思路：DFS、BFS 首先先看题目，给定的二维矩阵中，包含 ‘X’ 和 ‘O’（字母 O）。再看解释部分，任何边界上的 ‘O’ 不会被填充为 ‘X’，那么现在也就是说，其实有三个部分：

可形成包围的 ‘X’； 被 ‘X’ 包围的 ‘O’； 未被 ‘X’ 包围的 ‘O’。

现在题目的要求是将被包围的 ‘O’，转变为 ‘X’。前面也说了，未被包围的 ‘O’，是处于边界上的，同时侧面说明与边界 ‘O’ 相连的 ‘O’ 又不会被 ‘X’ 填充。

那么我们可以根据这个性质，我们考虑从边界开始扩散，先去标记不能被填充的 ‘O’，也就是与边界 ‘O’ 相连的部分，那么剩下的 ‘O’ 则会被包围转变为 ‘X’。具体的做法如下：

以边界的 ‘O’ 为起点，标记与之相连或者间接相连的字母 ‘O’； 当标记完上面部分的 ‘O’，此时开始遍历矩阵，去判断每个字母（注意：标记的为不会被替换的部分）：

如果该字母是被标记的部分，那么将其重新转换为 ‘O’； 如果该字母是未被标记的部门，那么将其转换为 ‘X’。 注意：题目要求的是原地修改，那么我们标记的时候，将与边界 ‘O’ 相连的部分（包括边界 ‘O’），标记为 ‘M’。

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

        def dfs(board, i, j):
            # 不处于矩阵内，或者如果已经标记的话，直接跳过
            if not (0<=i<m) or not (0<=j<n) or board[i][j] != O:
                return
            
            # 当确认为未标记的，并与边界 O 直接间接相连的 O 时，标记为 M
            board[i][j] = M
            # 向四个方位扩散
            # 上下左右
            dfs(board, i-1, j)
            dfs(board, i+1, j)
            dfs(board, i, j-1)
            dfs(board, i, j+1)
            

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

        # 从边界的 O 开始搜索
        for i in range(m):
            for j in range(n):
                # 先确认 i，j 是否处于边界
                is_frontier = (i == 0 or j == 0 or i == m-1 or j == n-1)
                if is_frontier and board[i][j] == O:
                    dfs(board, i, j)
        
        # 遍历二维数组，将被标记为 M 的重新转换为 O，未标记的，则转换为 X
        for i in range(m):
            for j in range(n):
                if board[i][j] == O:
                    board[i][j] = X
                if board[i][j] == M:
                    board[i][j] = O