题目大意 共 KKK 组测试数据，每组测试数据给出一个 A∗B∗CA * B * CA∗B∗C 的立方体，Jerry 每分钟能够移动到相邻六个坐标其中的一个，求是否能在不超过 TTT 分钟从 (1,1,1)(1,1,1)(1,1,1) 到 (A,B,C)(A, B, C)(A,B,C) ，如果能输出最少时间，如果不能则输出 −1-1−1。 题意分析 由于 Jerry 每次移动只需要 111 分钟，所以移动步数即分钟数。 求出 (1,1,1)(1,1,1)(1,1,1) 到 (A,B,C)(A,B,C)(A,B,C) 的最少移动步数跟 TTT 进行比较即可。 解题思路 广度优先搜索求出起点 (1,1,1)(1,1,1)(1,1,1) ，终点 (A,B,C)(A,B,C)(A,B,C) 的最少移动步数。 每次移动有六个方向，分别为 (1,0,0)(1,0,0)(1,0,0)， (−1,0,0)(-1,0,0)(−1,0,0)，(0,1,0)(0,1,0)(0,1,0)，(0,−1,0)(0,-1,0)(0,−1,0)，(0,0,1)(0,0,1)(0,0,1)，(0,0,−1)(0,0,-1)(0,0,−1) 。 时间复杂度解析 本题时间复杂度为 O(K⋅A⋅B⋅C)O(K \cdot A \cdot B \cdot C)O(K⋅A⋅B⋅C) 代码演示

这题可以用广度优先搜索（BFS）来解，可以直接套模板

#include <iostream> #include <cstring> #include <queue> using namespace std; const int max_n = 55; // 六个拓展方向 int dx[] = {1, -1, 0, 0, 0, 0}; int dy[] = {0, 0, 1, -1, 0, 0}; int dz[] = {0, 0, 0, 0, 1, -1}; int a, b, c, t; int mp[max_n][max_n][max_n]; int st[max_n][max_n][max_n]; struct Node { int x, y, z, step; }; // 检测坐标是否符合要求 int check(int i, int j, int k) { if (i <= 0 || j <= 0 || k <= 0 || i > a || j > b || k > c || mp[i][j][k]) return 0; return 1; } int bfs(int x, int y, int z) { queue<Node> Q; Q.push({x, y, z, 0}); st[x][y][z] = 1; while (!Q.empty()) { Node p = Q.front(); Q.pop(); if (p.x == a && p.y == b && p.z == c && p.step <= t) return p.step; for (int i = 0; i < 6; i++) { Node q = {p.x + dx[i], p.y + dy[i], p.z + dz[i], p.step + 1}; if (!st[q.x][q.y][q.z] && check(q.x, q.y, q.z)) { st[q.x][q.y][q.z] = 1; Q.push(q); } } } return -1; } int main() { int T; scanf("%d", &T); while (T--) { memset(mp, 0, sizeof(mp)); memset(st, 0, sizeof(st)); } return 0; }