自动搬运

查看原文

来自洛谷，原作者为

	DHT666 听自己的歌，写自己的故事。​

搬运于2025-08-24 22:52:57，当前版本为作者最后更新于2024-01-24 17:08:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给出一个边长为 $n$ 三维地图，有的点会有障碍，求由给出的起点到终点的最优路径。

思路

三维广搜，和二维的差不多，方向数组多开一个即可，注意不能斜着走，一次最多改变一个坐标的值。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 110;

int n;
int Map[N][N][N]; // 存障碍
int len[N][N][N]; // 存答案
bool vis[N][N][N]; // 标记

int dx[] = {0,0,0,0,0,1,-1}; // 方向数组
int dy[] = {0,0,0,1,-1,0,0};
int dz[] = {0,1,-1,0,0,0,0};

struct node {
	int x,y,z; // 坐标
}qd,zd;

void bfs() {
	queue <node> q;
	q.push(qd);
	vis[qd.x][qd.y][qd.z] = 1;
	while(q.size()) {
		int nx = q.front().x,ny = q.front().y,nz = q.front().z;
		q.pop();
		if(nx == zd.x && ny == zd.y && nz == zd.z) { // 到达终点
			cout<<len[nx][ny][nz];
			return ;
		}
		for(int i=1;i<=6;i++) {
			int qx = nx + dx[i];
			int qy = ny + dy[i];
			int qz = nz + dz[i];
			if(qx > n || qx < 1 || qy > n || qy < 1 || qz > n || qz < 1) continue; // 边界
			if(!vis[qx][qy][qz] && !Map[qx][qy][qz]) { // 可以走
				node tot; tot.x = qx,tot.y= qy,tot.z = qz;
				q.push(tot);
				vis[qx][qy][qz] = 1;
				len[qx][qy][qz] = len[nx][ny][nz] + 1; // 累加答案
			}
		}
	}
	cout<<-1; // 无解
}

int main() {
	cin>>n>>qd.x>>qd.y>>qd.z>>zd.x>>zd.y>>zd.z;
	
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			for(int k=1;k<=n;k++) {
				char x; cin>>x;
				Map[j][k][i] = x - '0'; // 注意顺序
			}
		}
	}
	
	bfs();
	
	return 0;
}