HDOJ 1240 Asteroids!：三维网格 BFS 最短路径

题目大意

N×N×N 立方体网格（N≤10），O 空地，X 小行星。从起点到终点，六向移动（上下左右前后），求最少步数。无路输出 NO ROUTE。

三维 BFS

• 状态：(x,y,z,step)
• 六方向：(±1,0,0), (0,±1,0), (0,0,±1)
• 访问标记三维数组
• 队列广度优先搜索

C++ 实现

#include 
#include 
#include 
#include 
using namespace std;

const int N = 15;
char grid[N][N][N];
int vis[N][N][N];
int dx[6] = {0,0,1,-1,0,0}, dy[6] = {0,0,0,0,1,-1}, dz[6] = {1,-1,0,0,0,0};

struct Node { int x,y,z,step; };

int bfs(int n, int sx,int sy,int sz, int ex,int ey,int ez) {
    queue q;
    memset(vis, -1, sizeof(vis));
    vis[sx][sy][sz] = 0;
    q.push({sx,sy,sz,0});
    while (!q.empty()) {
        Node u = q.front(); q.pop();
        if (u.x==ex && u.y==ey && u.z==ez) return u.step;
        for (int i=0;i<6;++i) {
            int nx=u.x+dx[i], ny=u.y+dy[i], nz=u.z+dz[i];
            if (nx>=0&&nx=0&&ny=0&&nz> cmd >> n) {
        for (int i=0;i> grid[k][j][i]; // 注意输入顺序：slice 行 列
        int sx,sy,sz, ex,ey,ez;
        cin >> sx >> sy >> sz >> ex >> ey >> ez;
        cin >> cmd; // END
        int ans = bfs(n, sx,sy,sz, ex,ey,ez);
        if (ans >= 0) cout << n << " " << ans << endl;
        else cout << "NO ROUTE" << endl;
    }
    return 0;
}

输入顺序注意

输入为 N 个 slice，每 slice N 行 N 列。读入时 grid[slice][row][col]，代码中调整为 grid[k][j][i] 对应 (x,y,z)。

复杂度

• 状态数 ≤ 10³ = 1000
• BFS 瞬间完成