【DFS】130.被围绕的区域-CSDN博客

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/135654867

本文介绍了一个编程问题解决方案，通过深度优先搜索(DFS)在给定的字符矩阵中查找并标记未被X包围的所有O字符。方法涉及创建访问标记数组和四个边界方向的递归调用。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

法1：DFS

典型题目，牢记方法！

Python

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

        for i in range(m):
            for j in range(n):
                if (i == 0 or i == m-1 
                    or j == 0 or j == n-1
                    and board[i][j] == 'O'):
                    self.dfs(board, visited, i, j)
        
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O' and not visited[i][j]:
                    board[i][j] = 'X'
    
    def dfs(self, board, visited, i, j):
        if (i < 0 or i >= len(board) 
            or j < 0 or j >= len(board[0])
            or board[i][j] == 'X'
            or visited[i][j]):
            return
        visited[i][j] = True
        self.dfs(board, visited, i-1, j)
        self.dfs(board, visited, i+1, j)
        self.dfs(board, visited, i, j-1)
        self.dfs(board, visited, i, j+1)

Java

class Solution {
    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        if (m == 0 || n == 0) {
            return;
        }
        boolean[][] visitedO = new boolean[m][n]; // 没有被围绕的'O'位置记录
        for (int i = 0; i < n; ++i) { // 首行
            dfs(board, visitedO, 0, i, m, n);
        }
        for (int i = 0; i < n; ++i) { // 末行
            dfs(board, visitedO, m - 1, i, m, n);
        }
        for (int i = 0; i < m; ++i) { // 首列
            dfs(board, visitedO, i, 0, m, n);
        }
        for (int i = 0; i < m; ++i) { // 末列
            dfs(board, visitedO, i, n - 1, m, n);
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O' && !visitedO[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(char[][] board, boolean[][] visitedO, int i, int j, int m, int n) {
        if (i >= 0 && i < m 
                && j >= 0 && j < n 
                && board[i][j] == 'O' 
                && !visitedO[i][j]) {
            visitedO[i][j] = true;
            dfs(board, visitedO, i - 1, j, m, n);
            dfs(board, visitedO, i + 1, j, m, n);
            dfs(board, visitedO, i, j - 1, m, n);
            dfs(board, visitedO, i, j + 1, m, n);
        }
    }
}