出题人题解｜不做作业会被抓走

题目大意

共 $K$ 组测试数据，每组测试数据给出一个 $A * B * C$ 的立方体，Jerry 每分钟能够移动到相邻六个坐标其中的一个，求是否能在不超过 $T$ 分钟从 $(1,1,1)$ 到 $(A, B, C)$ ，如果能输出最少时间，如果不能则输出 $-1$。

题意分析

由于 Jerry 每次移动只需要 $1$ 分钟，所以移动步数即分钟数。

求出 $(1,1,1)$ 到 $(A,B,C)$ 的最少移动步数跟 $T$ 进行比较即可。

解题思路

广度优先搜索求出起点 $(1,1,1)$ ，终点 $(A,B,C)$ 的最少移动步数。

每次移动有六个方向，分别为 $(1,0,0)$， $(-1,0,0)$，$(0,1,0)$，$(0,-1,0)$，$(0,0,1)$，$(0,0,-1)$​。

时间复杂度解析

本题时间复杂度为 $O(K \cdot A \cdot B \cdot C)$

代码演示

#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));
 
    scanf("%d%d%d%d", &a, &b, &c, &t);
    for (int i = 1; i <= a; i++)
      for (int j = 1; j <= b; j++)
        for (int k = 1; k <= c; k++) 
		  scanf("%d", &mp[i][j][k]);
    printf("%d\n", bfs(1, 1, 1));
  }
 
  return 0;
}