编程挑战：求解被1包围的0的数量及DFS适配问题

首先得说，你的思路完全正确——计算被1包围的0的数量，等价于用总0的数量减去那些和矩阵边界相连的未被包围的0的数量，用DFS遍历边界可达的0是这类问题的常规解法，能通过前两组小数据测试（r、c≤1000）很合理。

不过如果第三组测试用例是更大规模的矩阵（比如r、c突破1000甚至到万级），递归式DFS大概率会遇到两个问题：

• 递归深度过大导致栈溢出：比如当矩阵是一条长链的0从边界延伸到中心，递归深度会达到矩阵的边长，超过大多数编程语言默认的栈大小限制。
• 递归的额外调用开销可能导致超时，大数据量下迭代式的实现效率会高很多。

给你几个针对性的优化方向：

1. 改用迭代式DFS或BFS #

把递归的DFS改成用栈模拟的迭代版本，或者直接用BFS（队列实现），这样能彻底避免栈溢出的问题，同时性能更稳定。比如BFS的思路就是从所有边界的0出发，把所有连通的未被包围的0标记出来，最后计算差值即可。

2. 避免构建完整矩阵（内存优化） #

如果矩阵尺寸很大，直接创建rc的二维数组会占用大量内存（比如1e41e4的矩阵就要1亿个元素）。你可以用一个哈希集合存储所有1的坐标，遍历的时候直接检查当前位置是否属于1，这样内存占用只和1的数量n相关，适合n远小于r*c的场景。

下面是一个Python实现的BFS示例代码，兼顾了上述两个优化点：

def count_surrounded_zeros(r, c, ones):
    # 将1的坐标存入集合，O(1)查询
    one_coords = set((i, j) for i, j in ones)
    visited = set()
    # 上下左右四个方向
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # 处理上下边界的所有列
    for col in range(c):
        for row in [0, r - 1]:
            if (row, col) not in one_coords and (row, col) not in visited:
                queue = [(row, col)]
                visited.add((row, col))
                while queue:
                    x, y = queue.pop(0)
                    for dx, dy in dirs:
                        nx, ny = x + dx, y + dy
                        # 检查是否在矩阵范围内，且不是1、未被访问
                        if 0 <= nx < r and 0 <= ny < c:
                            if (nx, ny) not in one_coords and (nx, ny) not in visited:
                                visited.add((nx, ny))
                                queue.append((nx, ny))
    # 处理左右边界（排除已经处理过的上下边界行）
    for row in range(1, r - 1):
        for col in [0, c - 1]:
            if (row, col) not in one_coords and (row, col) not in visited:
                queue = [(row, col)]
                visited.add((row, col))
                while queue:
                    x, y = queue.pop(0)
                    for dx, dy in dirs:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < r and 0 <= ny < c:
                            if (nx, ny) not in one_coords and (nx, ny) not in visited:
                                visited.add((nx, ny))
                                queue.append((nx, ny))
    # 总0数 = 总格子数 - 1的数量
    total_zeros = r * c - len(ones)
    # 被包围的0 = 总0数 - 未被包围的0数（visited的大小）
    return total_zeros - len(visited)

额外提示 #

如果是用C++、Java这类静态语言，你可以根据矩阵大小选择合适的标记方式：

• 若r*c不大，用二维布尔数组标记访问状态，速度更快；
• 若r*c过大，用哈希集合（比如C++的unordered_set）存储访问过的坐标，节省内存。

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