题解 | #Jelly#

链接：https://ac.nowcoder.com/acm/problem/201613
来源：牛客网

题目描述

思路：答案等同于求迷宫中最短路径步数，所以用bfs，这题无非是把二维给换成了三维，但是做法和二维一样，也是一道基础的模板题

直接用bfs模板做就好啦

bfs模板，来自 <https://www.luogu.com.cn/article/z35v1xn7>，非常简洁且好用！

 queue<node> q; 
void bfs(){ 
    while(!q.empty()) { 
        node temp=q.front(); 
        q.pop(); 
        if(完成目标) { 
            记录;
             return; 
        } 
        for(int i=0;i<m;i++)//m为方向数组长度 
        { 
            int xx=temp.x+dx[i]; 
            int yy=temp.y+dy[i]; 
            if(下标越界||已被标记) { 
                continue; 
            } 
            mark[xx][yy]=1;
            q.push(node{xx,yy});//注意，node{xx,yy}这种形式只适用于C++20及以上版本 
        } 
    }
}

代码如下：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
char s[120][120][120]; //存储图数组
int vis[120][120][120]; //存储状态数组
int dir[6][3]= {{1,0,0},{-1,0,0},{0,1,0},{0,0,1},{0,-1,0},{0,0,-1}}; //方向数组
int ans=-1,n;
struct node {
    int num,z,x,y;
};
queue<node>q; //STL的队列
void BFS() {
    while(!q.empty()) { //队列为空时退出循环
            node temp=q.front(); //取队列的第一个值
            q.pop();
            if(temp.x==n-1 && temp.y==n-1 && temp.z==n-1) { //如果队列中的x,y,z都到了终点，则获取其步数值
                ans=temp.num;
                return;
            }
            for(int i=0; i<6; i++) { //6个方向依次探索
                int zz=temp.z+dir[i][0];
                int xx=temp.x+dir[i][1];
                int yy=temp.y+dir[i][2];
                if(vis[zz][xx][yy] || xx<0 || yy<0 || zz<0 || xx>=n || yy>=n || zz>=n || s[zz][xx][yy]=='*') { //如果无法到达此处，则continue
                    continue;
                }
                vis[zz][xx][yy]=1; //更新此处状态
                q.push(node {temp.num+1,zz,xx,yy}); //将此坐标存入队列
            }
    }
}
int main() {
    scanf("%d",&n);
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            scanf("%s",s[i][j]);
        }
    }
    vis[0][0][0]=1; //更新起点状态
    q.push(node {1,0,0,0}); //记得把起点存入队列里再bfs，不然bfs没用
    BFS();
    printf("%d\n",ans);
    return 0;
}