P9909 [COCI 2023/2024 #2] Pingvin 题解

DHT666 · 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;
}