LeetCode SURROUNDED REGIONS问题运行报AddressSanitizer栈溢出错误求助

错误根因 #

你触发的是栈溢出错误，并非数组越界，核心是DFS递归出现无限循环，调用栈深度超过系统限制，具体问题如下：

• 无访问标记逻辑：你遍历到值为O的节点时没有做任何访问标记，当你从当前节点递归到相邻的O节点后，相邻节点又会反过来递归回当前节点，形成无限递归循环，直接撑爆栈空间。
• DFS逻辑不符合题意：你的逻辑是要求单个节点四个方向都返回true才标记为X，但实际上只要连通块中任意一个O和边界连通，整个连通块的所有O都不能修改，单节点判断逻辑无法正确识别连通块的属性。

正确实现思路 #

采用反向排除的思路处理，避免无效递归：

1. 先遍历矩阵的四条边界，把所有边界上的O以及和这些边界O连通的O都标记为临时字符（比如A），标记过程中同步标记已访问，避免重复递归。
2. 遍历整个矩阵做最终转换：
   • 遇到剩余的O，说明是被围绕的，直接改成X
   • 遇到之前标记的A，改回原来的O

修正后代码示例 #

void dfs(int i, int j, int m, int n, vector<vector<char>>& board) {
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
        return;
    }
    // 标记为临时字符，避免重复访问
    board[i][j] = 'A';
    dfs(i - 1, j, m, n, board);
    dfs(i + 1, j, m, n, board);
    dfs(i, j - 1, m, n, board);
    dfs(i, j + 1, m, n, board);
}

void solve(vector<vector<char>>& board) {
    int m = board.size();
    if (m == 0) return;
    int n = board[0].size();
    // 遍历上下边界
    for (int j = 0; j < n; j++) {
        dfs(0, j, m, n, board);
        dfs(m - 1, j, m, n, board);
    }
    // 遍历左右边界
    for (int i = 1; i < m - 1; i++) {
        dfs(i, 0, m, n, board);
        dfs(i, n - 1, m, n, board);
    }
    // 最终转换
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') {
                board[i][j] = 'X';
            } else if (board[i][j] == 'A') {
                board[i][j] = 'O';
            }
        }
    }
}

内容的提问来源于stack exchange，提问作者Asking_questions