题目链接:1240
思路:BFS搜索,采用队列实现,搜索的层级即为步数。
代码如下:
#include<bits/stdc++.h>
using namespace std;
struct point{
int x,y,z,w; //w表示BFS搜索的深度
bool operator ==(const point &p); //运算符重载判断结构体是否相等
};
bool point::operator==(const point&p){
return ((x==p.x)&&(y==p.y)&&(z==p.z));
}
char road[10][10][10];
int dir[6][3]={
{1,0,0},
{-1,0,0},
{0,1,0},
{0,-1,0},
{0,0,1},
{0,0,-1}
};
bool inmap(point p,int N){
int x=p.x,y=p.y,z=p.z;
if(x>=0&&x<N){
if(y>=0&&y<N){
if(z>=0&&z<N){
return true;
}
}
}
return false;
}
bool safe(point p){
if(road[p.x][p.y][p.z]=='O'){
return true;
}
return false;
}
int BFS(int n,point start,point end){
if(start==end){
return 0;
}
queue<point>op;
point next,s;
op.push(start);
while(!op.empty()){
s=op.front();
op.pop();
for(int i=0;i<6;i++){
next.x=s.x+dir[i][0];
next.y=s.y+dir[i][1];
next.z=s.z+dir[i][2];
next.w=s.w+1;
if(inmap(next,n)&&safe(next)){
op.push(next);
road[next.x][next.y][next.z]='X';
}
//找到目标
if(next==end){
return next.w;
}
}
}
return -1;
}
int main(){
string s;
int n,step=0;
point start,end;
while(cin>>s>>n){
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>road[i][j][k];
}
}
}
cin>>start.x>>start.y>>start.z;
cin>>end.x>>end.y>>end.z;
cin>>s;
start.w=0;
end.w=0;
int ans=BFS(n,start,end);
if(ans>=0){
cout<<n<<" "<<ans<<endl;
}
else{
cout<<"NO ROUTE"<<endl;
}
}
return 0;
}