被围绕的区域

难度: Medium

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

示例 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"]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'

Submission

运行时间: 20 ms

内存: 20.5 MB

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        dirs = [[-1,0],[1,0],[0,1],[0,-1]]
        rows = len(board)
        cols = len(board[0])
        visited = [[False] * cols for _ in range(rows)]

        def in_area(row,col):
            return 0 <= row < rows and 0 <= col < cols
        
        def dfs(row,col):
            if not in_area(row,col) or board[row][col] == 'X' or visited[row][col]:
                return 
            visited[row][col] = True
            for d in dirs:
                next_row = row + d[0]
                next_col = col + d[1]
                dfs(next_row,next_col)
        for col in range(cols):
            if board[0][col] == 'O' and not visited[0][col]:
                dfs(0, col)
            if board[rows - 1][col] == 'O' and not visited[rows - 1][col]:
                dfs(rows - 1, col)

        for row in range(1, rows - 1):
            if board[row][0] == 'O' and not visited[row][0]:
                dfs(row, 0)
            if board[row][cols - 1] == 'O' and not visited[row][cols - 1]:
                dfs(row, cols - 1)

        for row in range(1, rows - 1):
            for col in range(1, cols - 1):
                if board[row][col] == 'O' and not visited[row][col]:
                    board[row][col] = 'X'

Explain

这个题解采用了深度优先搜索（DFS）的方法。首先对矩阵的四条边界上的 'O' 进行 DFS，标记所有与边界 'O' 相连的 'O'，这些 'O' 不会被填充为 'X'。然后遍历矩阵内部，将所有未被标记的 'O' 填充为 'X'。

时间复杂度: O(mn)

空间复杂度: O(mn)

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        dirs = [[-1,0],[1,0],[0,1],[0,-1]]  # 四个方向：上、下、右、左
        rows = len(board)  # 矩阵的行数
        cols = len(board[0])  # 矩阵的列数
        visited = [[False] * cols for _ in range(rows)]  # 标记格子是否访问过

        def in_area(row,col):  # 判断坐标 (row, col) 是否在矩阵内
            return 0 <= row < rows and 0 <= col < cols
        
        def dfs(row,col):  # 深度优先搜索
            if not in_area(row,col) or board[row][col] == 'X' or visited[row][col]:
                return 
            visited[row][col] = True
            for d in dirs:  # 向四个方向扩展
                next_row = row + d[0]
                next_col = col + d[1]
                dfs(next_row,next_col)
                
        # 对左右两条竖边进行 DFS
        for col in range(cols):
            if board[0][col] == 'O' and not visited[0][col]:
                dfs(0, col)
            if board[rows - 1][col] == 'O' and not visited[rows - 1][col]:
                dfs(rows - 1, col)
        
        # 对上下两条横边进行 DFS
        for row in range(1, rows - 1):
            if board[row][0] == 'O' and not visited[row][0]:
                dfs(row, 0)
            if board[row][cols - 1] == 'O' and not visited[row][cols - 1]:
                dfs(row, cols - 1)
        
        # 将所有未标记的 'O' 填充为 'X'
        for row in range(1, rows - 1):
            for col in range(1, cols - 1):
                if board[row][col] == 'O' and not visited[row][col]:
                    board[row][col] = 'X'

Explore

递归深度的估计是基于最坏情况下，从一个边界的'O'开始，沿着可能的路径一直搜索到矩阵的另一个边界。在一个m行n列的矩阵中，最长的搜索路径可能是从矩阵的一个角开始，对角线到达另一个角，此路径长度大约是m+n。但实际上，由于DFS会从四个方向进行扩展，遍历的路径可能会因为路径重叠而少于m+n。严格来说，这个估计是一个上限，实际使用的递归深度可能会小于这个值，但不会超过，除非有环形的连通区域，这在本题的情境中是不会出现的。

在DFS中，使用`visited`数组是为了防止重复访问相同的节点，这可以避免无限循环和不必要的重复计算。每个节点（即矩阵中的每个位置）只需要被访问一次，以判断它是否与边界的'O'直接或间接相连。如果不使用`visited`标记，DFS可能会反复进入已访问过的节点，导致递归无法正确结束，程序效率也会显著降低。

这种策略的基本思想是：只有与边界上的'O'直接或间接相连的内部'O'才是安全的，不会被包围。因此，从边界上的每个'O'出发进行DFS，可以标记所有这些安全的'O'。通过这种方式，所有从边界可达的'O'都会被访问并标记，而那些没有被标记的'O'则意味着它们是被完全包围的，可以安全地被转换为'X'。

确实，对于非常大的矩阵，使用递归的DFS可能会导致栈溢出。一个可行的替代方法是使用广度优先搜索（BFS），它使用队列而不是调用栈来处理节点，这可以有效防止栈溢出问题。BFS按层次扩散，每次处理所有当前层的节点，然后移动到下一层，这样可以避免深度递归导致的栈溢出风险。另一个方法是将递归DFS转换为迭代DFS，通过手动维护一个栈来模拟递归调用，这样也可以控制栈的大小，避免溢出。