求助：我的BFS算法返回步数多1，部分网格结果正常

我在学习BFS（广度优先搜索）算法时，发现实现存在步数计算错误：当目标为网格右下角（grid[grid.Length - 1][grid.Length - 1]）时，返回值比正确步数多1。

测试案例 #

测试网格1 #

int[][] grid = new[]
{
    new int[] { 0, 0, 0 },
    new int[] { 1, 1, 0 },
    new int[] { 1, 1, 0 }
};

该网格下算法返回5，正确步数应为4。

测试网格2 #

int[][] grid = new[]
{
    new int[] { 0, 1},
    new int[] { 1, 0}
};

算法返回正确值2。为何两个网格结果不一致？

我的BFS算法实现 #

int[][] dirs = new[]
{
    new[] { 0, 1 }, //下
    new[] { 1, 1 }, //右下
    new[] { 1, 0 }, //右
    new[] { 1, -1 }, //右上
    new[] { 0, -1 }, //上
    new[] { -1, -1 }, //左上
    new[] { -1, 0 }, //左
    new[] { -1, 1 } //左下
};

public int BinaryMatrix(int[][] grid)
{
    /* 行数 */
    var rowLength = grid.Length;

    /* 列数 */
    var colLength = grid[0].Length;

    /* 起点或终点为障碍，直接返回-1 */
    if (grid[0][0] == 1 || grid[rowLength - 1][colLength - 1] == 1)
        return -1;

    var Queue = new Queue<int[]>(); /* 存储坐标 */

    /* 创建访问标记数组，避免修改原网格 */
    int[][] visited = new int[rowLength][];

    for (int i = 0; i < visited.Length; i++)
        visited[i] = new int[colLength];

    Queue.Enqueue(new[] { 0, 0 });
    visited[0][0] = 1;
    int steps = 1;

    while (Queue.Count != 0)
    {
        int[] coord = Queue.Dequeue();

        var cy = coord[0]; /* Y坐标 */
        var cx = coord[1]; /* X坐标 */

        /* 判断当前弹出的坐标是否为终点 */
        if (cy == rowLength - 1 && cx == colLength - 1) return steps;

        for (int i = 0; i < dirs.Length; i++)
        {
            int neighborY = dirs[i][0] + cy;
            int neighborX = dirs[i][1] + cx;

            /* 边界检查 */
            if (neighborX >= 0 && neighborX < colLength && neighborY >= 0 && neighborY < rowLength)
            {
                /* 未访问且不是障碍 */
                if (visited[neighborY][neighborX] == 0 && grid[neighborY][neighborX] == 0)
                {
                    Queue.Enqueue(new[] { neighborY, neighborX });
                    visited[neighborY][neighborX] = 1;
                }
            }
        }
        steps++;
    }
    return -1;
}

问题原因分析 #

你的BFS步数计算逻辑存在层级处理错误：当前代码每弹出一个节点就递增steps，但BFS应该按「层级」计算步数——即每处理完一层所有节点，才增加一步。

• 测试网格2中，起点(0,0)的邻居直接是终点(1,1)：弹出起点后判断不是终点，处理邻居加入队列，steps从1变为2；下一次循环弹出终点，返回steps=2，刚好正确。
• 测试网格1中，路径是(0,0) → (0,1) → (0,2) → (1,2) → (2,2)，共4步。但代码流程是：
  1. 弹出(0,0)，不是终点，处理邻居后steps变为2；
  2. 弹出(0,1)，不是终点，处理邻居后steps变为3；
  3. 弹出(0,2)，不是终点，处理邻居后steps变为4；
  4. 弹出(1,2)，不是终点，处理邻居后steps变为5；
  5. 弹出(2,2)，此时返回steps=5，比正确值多1。

核心问题：没有按层级批量处理节点，单个节点处理后就加步数，导致终点被弹出时，步数已多算一次。

修复方案 #

修改BFS逻辑，每次循环处理当前队列中所有节点（即当前层级的所有节点），处理完整个层级后再递增步数：

int[][] dirs = new[]
{
    new[] { 0, 1 }, //下
    new[] { 1, 1 }, //右下
    new[] { 1, 0 }, //右
    new[] { 1, -1 }, //右上
    new[] { 0, -1 }, //上
    new[] { -1, -1 }, //左上
    new[] { -1, 0 }, //左
    new[] { -1, 1 } //左下
};

public int BinaryMatrix(int[][] grid)
{
    var rowLength = grid.Length;
    var colLength = grid[0].Length;

    if (grid[0][0] == 1 || grid[rowLength - 1][colLength - 1] == 1)
        return -1;

    var queue = new Queue<int[]>();
    int[][] visited = new int[rowLength][];
    for (int i = 0; i < visited.Length; i++)
        visited[i] = new int[colLength];

    queue.Enqueue(new[] { 0, 0 });
    visited[0][0] = 1;
    int steps = 1;

    while (queue.Count != 0)
    {
        // 获取当前层级的节点数量
        int levelSize = queue.Count;
        // 处理当前层级的所有节点
        for (int j = 0; j < levelSize; j++)
        {
            int[] coord = queue.Dequeue();
            var cy = coord[0];
            var cx = coord[1];

            if (cy == rowLength - 1 && cx == colLength - 1)
                return steps;

            for (int i = 0; i < dirs.Length; i++)
            {
                int neighborY = dirs[i][0] + cy;
                int neighborX = dirs[i][1] + cx;

                if (neighborX >= 0 && neighborX < colLength && neighborY >= 0 && neighborY < rowLength)
                {
                    if (visited[neighborY][neighborX] == 0 && grid[neighborY][neighborX] == 0)
                    {
                        queue.Enqueue(new[] { neighborY, neighborX });
                        visited[neighborY][neighborX] = 1;
                    }
                }
            }
        }
        // 处理完整个层级后，步数加1
        steps++;
    }
    return -1;
}

验证结果 #

• 测试网格1：路径层级为(0,0) → [(0,1)] → [(0,2)] → [(1,2)] → [(2,2)]，处理(2,2)时返回steps=4，正确。
• 测试网格2：层级为(0,0) → [(1,1)]，处理(1,1)时返回steps=2，正确。

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