BFS · 迷宫最短路

CSP-J · 编程模板 · 代码 · cpp · 难度 4/5 · 共 877 字

按层扩展，首次到达即最短步数

广搜
最短路

前置内容

队列 · 模拟

正文

// ── 广搜（BFS）迷宫最短步数 ──
// 一圈一圈向外扩散：
// 第一次到终点时步数一定最短
struct Node { int x, y, step; } q[10005];
int head = 0, tail = 0, ans = -1;
// 起点入队
q[tail].x = sx; q[tail].y = sy;
q[tail].step = 0; tail++;
// 入队立刻标记，防重复入队
vis[sx][sy] = 1;
while (head < tail) {
    // 取出队首扩展
    struct Node u = q[head++];
    if (u.x == tx && u.y == ty) {
        // 首次到达即最短
        ans = u.step;
        break;
    }
    // 上下左右四个方向
    for (int k = 0; k < 4; k++) {
        int nx = u.x + dx[k];
        int ny = u.y + dy[k];
        // 出界
        if (nx < 1 || nx > n) continue;
        if (ny < 1 || ny > m) continue;
        // 墙或走过
        if (vis[nx][ny]) continue;
        if (g[nx][ny] == '#') continue;
        vis[nx][ny] = 1;
        q[tail].x = nx;
        q[tail].y = ny;
        q[tail].step = u.step + 1;
        tail++;
    }
}
printf("%d", ans);
// 分工：BFS 求「最少步数」
// DFS 求「能否到达 / 所有方案」

BFS · 迷宫最短路

前置内容

正文

CSP-J · 编程模板的其它内容