第36602题 组合题
完善程序(第二题):BFS 求迷宫最短步数

下面的程序用广度优先搜索(BFS)在一个 n 行 m 列的 0/1 网格中,求从起点 (sx, sy) 到终点 (tx, ty) 的最短步数。0 表示可通行的格子,1 表示障碍;若终点不可达则输出 -1。队列用数组 qx、qy 配合头指针 head、尾指针 tail 模拟。试补全程序。

#include <cstdio>

int n, m;
int g[105][105], dis[105][105];
int qx[10005], qy[10005];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &g[i][j]);
    int sx, sy, tx, ty;
    scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            dis[i][j] = -1;
    int head = 1, tail = 0;
    qx[++tail] = sx;
    qy[tail] = sy;
    dis[sx][sy] = ___①___;
    while (___②___) {
        int x = qx[head], y = qy[head];
        ___③___
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == 0 &&
                ___④___) {
                dis[nx][ny] = dis[x][y] + 1;
                qx[++tail] = nx;
                ___⑤___
            }
        }
    }
    printf("%d\n", dis[tx][ty]);
    return 0;
}
{{ option.label }}
子题{{ index + 1 }} {{ child.type_label }}
{{ option.label }}
✓ 正确 ◐ 部分正确 ✗ 错误
程序运行统计
暂无判题统计
知识点:
提交{{ questionInfo.stats ? questionInfo.stats.submit_count : 0 }}次 正确率{{ statsAccuracy }}%
答案解析