出题组题解 | CXXP#1 T3

T3 皮皮虾的3D迷宫

• 难度：普及/提高-
• 思路：用 BFS，先保证字典序，最后回溯从终点倒推，输出即可。

#include<bits/stdc++.h>
using namespace std;
int n,bx,by,bz,ex,ey,ez,vis[21][21][21],sum[21][21][21];
char c[21][21][21];
int dir[7][3]={{0,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1},{1,0,0},{-1,0,0}}; 
struct node
{
	int x,y,z,step;
}pre[21][21][21],l,r;
void bfs(int x,int y,int z)
{
    queue<node>q;
    q.push({x,y,z,0});
    while(!q.empty())
    {
    	l=q.front();
    	q.pop();
    	for(int i=1;i<=6;i++)
    	{
    		r.x=l.x+dir[i][0],r.y=l.y+dir[i][1],r.z=l.z+dir[i][2],r.step=l.step+1;
    		if(r.x>=1 && r.x<=n && r.y>=1 && r.y<=n && r.z>=1 && r.z<=n && !vis[r.x][r.y][r.z] && c[r.x][r.y][r.z]!='#')
    		{
    			vis[r.x][r.y][r.z]=1;
    			sum[r.x][r.y][r.z]=r.step;
    			pre[r.x][r.y][r.z]={l.x,l.y,l.z,0};
                if(c[r.x][r.y][r.z]=='E')return;
    			q.push(r);
			}
		}
	}
	return;
}
void input()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                cin>>c[i][j][k];
                if(c[i][j][k]=='S')bx=i,by=j,bz=k;
                if(c[i][j][k]=='E')ex=i,ey=j,ez=k;
            }
        }
    }
    memset(sum,0x3f,sizeof(sum));
    sum[bx][by][bz]=0;
    vis[bx][by][bz]=1;
    return;
}
void print(int x,int y,int z)
{
    if(c[x][y][z]=='S')
	{
		cout<<"("<<y-1<<","<<z-1<<","<<x-1<<")";
		return;
	}
	//cout<<x<<" "<<y<<" "<<z<<" "<<pre[x][y][z].x<<" "<<pre[x][y][z].y<<" "<<pre[x][y][z].z<<endl;
	print(pre[x][y][z].x,pre[x][y][z].y,pre[x][y][z].z);
	cout<<"->("<<y-1<<","<<z-1<<","<<x-1<<")";
	return;
}
int main()
{
    input();
    bfs(bx,by,bz);
    if(!vis[ex][ey][ez])
    {
        cout<<-1;
        return 0;
    }
    cout<<sum[ex][ey][ez]<<endl;
    //print(ex,ey,ez);
    return 0;
}

题解仅供学习参考使用。
抄袭、复制题解，以达到刷 AC 率/AC 数量或其他目的的行为，在 ACGO 是严格禁止的。