题解思路

这道题目是一个典型的三维空间中的广度优先搜索（BFS）问题。我们需要在三维矩阵中找到从起始位置到目标位置的最短路径，每次移动只能沿六个方向之一（上下左右前后）移动一步，且不能穿过小行星（'X'）。

步骤如下：

1. 输入处理：读取每个测试用例的切片数据，构建三维矩阵。
2. BFS初始化：从起始位置开始，使用队列进行广度优先搜索，记录到达每个位置的最小步数。
3. 方向移动：每次从队列中取出一个位置，尝试向六个方向移动，如果移动后的位置是空区域（'O'）且未被访问过，则将其加入队列。
4. 终止条件：如果到达目标位置，记录当前步数；如果队列为空仍未到达目标位置，则输出无路径。

解决代码

#include<iostream>
#include<queue>
using namespace std;
#include<cstring>
#define INF 0x3f3f3f3f

struct node {
    int x, y, z;
    int level;
    node(int i, int j, int k, int l) : x(i), y(j), z(k), level(l) {};
    void set(int i, int j, int k, int l) {
        x = i;
        y = j;
        z = k;
        level = l;
    }
};

int d[6][3] = {{0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}, {0, 0, 1}, {0, 0, -1}};
char m[10][10][10];
bool used[10][10][10];
int s[3], e[3];
int n, step;
queue<node> q;

void bfs(int x, int y, int z) {
    int i, j, k, l;
    node pos(x, y, z, 0);
    q.push(pos);
    used[x][y][z] = 1;
    while (!q.empty()) {
        pos = q.front();
        i = pos.x;
        j = pos.y;
        k = pos.z;
        l = pos.level;
        q.pop();
        if (i == e[0] && j == e[1] && k == e[2]) {
            if (l < step)
                step = l;
            continue;
        }
        for (int t = 0; t < 6; t++) {
            x = i + d[t][0];
            y = j + d[t][1];
            z = k + d[t][2];
            if (x < 0 || x >= n || y < 0 || y >= n || z < 0 || z >= n || m[x][y][z] != 'O' || used[x][y][z])
                continue;
            pos.set(x, y, z, l + 1);
            used[x][y][z] = 1;
            q.push(pos);
        }
    }
}

int main() {
    char str[6];
    while (cin >> str >> n) {
        memset(used, 0, sizeof used);
        step = INF;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    cin >> m[i][j][k];
        cin >> s[0] >> s[1] >> s[2] >> e[0] >> e[1] >> e[2];
        cin >> str;
        bfs(s[0], s[1], s[2]);
        if (step != INF)
            cout << n << " " << step << endl;
        else
            cout << "NO ROUTE" << endl;
    }
    return 0;
}

代码解释

• 结构体 node：用于存储三维坐标和当前步数。
• 方向数组 d：定义了六个可能的移动方向（上下左右前后）。
• 三维矩阵 m：存储每个位置是空区域（'O'）还是小行星（'X'）。
• BFS函数：从起始位置开始，逐层搜索可能的路径，直到找到目标位置或队列为空。
• 输入处理：读取每个测试用例的切片数据、起始位置和目标位置，调用BFS进行搜索，并输出结果。

通过BFS确保找到的路径是最短的，利用队列实现层次遍历，每次处理一层（即步数相同的位置），直到找到目标位置。