JS解决LeetCode 542.01矩阵遇无限循环，求优化方案

我尝试解决LeetCode 542. 01矩阵问题时出现了无限循环。该问题要求：给定一个m×n的二进制矩阵mat，返回每个单元格到最近0的距离，相邻单元格间距离为1。示例输入为mat = [[0,0,0],[0,1,0],[0,0,0]]，输出与输入一致。

用户提交的代码：

var updateMatrix = function (mat) {
    const m = mat.length
    const n = mat[0].length
    for (let y = 0; y < m; y++) {
        for (let x = 0; x < n; x++) {
            if (mat[y][x] !== 0) {
                mat[y][x] = Infinity
            }
        }
    }
    const bfs = (y, x, selfVal) => {
        if (y < 0 || x < 0 || y > m - 1 || x > n - 1) {
            return
        }
        if (mat[y][x] !== 0) {
            mat[y][x] = Math.min(selfVal + 1, mat[y][x])
        }
        bfs(y + 1, x, mat[y][x])
        bfs(y - 1, x, mat[y][x])
        bfs(y, x + 1, mat[y][x])
        bfs(y, x - 1, mat[y][x])
    }
    bfs(0, 0, mat[0][0])
    return mat
};

问题分析 #

1. 思路方向错误：你用的是递归DFS而非BFS，而且仅从(0,0)单个起点出发，无法确保每个单元格找到最近的0——比如矩阵右下角的单元格可能离其他0更近，但会被从(0,0)扩散来的较大值覆盖。
2. 无限循环直接原因：递归调用没有访问限制，比如访问(0,0)后会调用(0,1)，(0,1)又会回调(0,0)，来回往复，没有任何机制阻止这种反向调用。

正确解法：多源BFS #

解决这个问题的标准方法是多源BFS，把所有0的位置作为初始队列，逐层向外扩展，这样每个单元格第一次被访问时的距离就是到最近0的距离，同时用visited标记已处理单元格，彻底避免循环。

修复后的代码：

var updateMatrix = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    const queue = [];
    const visited = new Array(m).fill().map(() => new Array(n).fill(false));

    // 初始化：所有0入队并标记已访问
    for (let y = 0; y < m; y++) {
        for (let x = 0; x < n; x++) {
            if (mat[y][x] === 0) {
                queue.push([y, x]);
                visited[y][x] = true;
            } else {
                mat[y][x] = Infinity;
            }
        }
    }

    // 四个相邻方向
    const dirs = [[-1,0], [1,0], [0,-1], [0,1]];

    while (queue.length > 0) {
        const [y, x] = queue.shift();
        for (const [dy, dx] of dirs) {
            const ny = y + dy;
            const nx = x + dx;
            // 检查边界+未访问
            if (ny >= 0 && ny < m && nx >=0 && nx < n && !visited[ny][nx]) {
                mat[ny][nx] = mat[y][x] + 1;
                visited[ny][nx] = true;
                queue.push([ny, nx]);
            }
        }
    }

    return mat;
};

关键说明 #

• 多源启动：所有0同时作为BFS起点，保证每个单元格第一次被遍历到的距离就是最近的0的距离，不会出现距离覆盖错误。
• visited数组：标记已处理的单元格，防止重复入队和反向访问，彻底解决无限循环问题。

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