130. 被围绕的区域

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/surrounded-regions

题目

给定一个二维的矩阵，蕴含 ‘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’。如果两个元素在程度或垂直方向相邻，则称它们是“相连”的。

解题思路

思路：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’。

咱们当初应用深度优先搜寻（DFS）和广度优先搜寻（BFS）的办法来解决这个问题。具体的代码如下。

代码实现

# 深度优先搜寻（DFS）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'

# 广度优先搜寻（BFS）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
        
        m = len(board)
        n = len(board[0])

        from collections import deque
        queue = deque()

        # bfs 不同于 dfs 顺着满足条件的方向持续搜寻
        # bfs 满足条件的都要入队列
        # 先将边界的 'O' 入队
        for i in range(m):
            # 这里是二维矩阵的最左列与最右列
            if board[i][0] == 'O':
                queue.append((i, 0))
            if board[i][n-1] == 'O':
                queue.append((i, n-1))
        
        for j in range(n):
            # 这里是二维矩阵的第一行和最初一行
            if board[0][j] == 'O':
                queue.append((0, j))
            if board[m-1][j] == 'O':
                queue.append((m-1, j))
        
        # 当初开始出队，目前外面的都是边界的 'O'
        # 出队的同时，进行标记，同时查找与边界 'O' 相连的局部入队
        while queue:
            x, y = queue.popleft()
            board[x][y] = 'M'
            # 查找相连局部
            for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
                if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'O':
                    queue.append((nx, ny))
        
        # 同样的，标记完后，遍历整个二维矩阵，进行转换
        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'

实现后果

欢送关注

公众号【书所集录】