hdu1240 Asteroids! （三维BFS）

Problem - 1240 (hdu.edu.cn)

三维的BFS，存在一个坐标点的变换，即输入的是 (y , z , x)，进行转换即可

#include<iostream> 
#include<queue>
#include<cstring>
using namespace std;
int n,x1,y1,z1,x2,y2,z2,flag,vis[20][20][20];
char room[20][20][20];
struct node{
    int x,y,z,step;
};
#define CHECK(x,y,z) (x>=0&&x<n&&y>=0&&y<n&&z>=0&&z<n)
int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
void BFS(){
    queue<node> q;
    node start,next;
    start.x=x1;
    start.y=y1;
    start.z=z1;
    start.step=0;
    q.push(start);
    flag=0;
    while(!q.empty()){
        start=q.front();
        q.pop();
        if(start.x==x2 && start.y==y2 && start.z==z2){
            cout<<n<<" "<<start.step<<endl;
            flag=1;
            break;
        }
        for(int i=0;i<6;i++){
            next.x=start.x+dir[i][0];
            next.y=start.y+dir[i][1];
            next.z=start.z+dir[i][2];
            if(CHECK(next.x,next.y,next.z) && vis[next.x][next.y][next.z]!=-1){
                vis[next.x][next.y][next.z]=-1;
                next.step=start.step+1;
                q.push(next);
            }
        }    
    }
    if(!flag) cout<<"NO ROUTE"<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s;
    while(cin>>s){
        cin>>n;
        memset(vis,0,sizeof(vis));
        memset(room,0,sizeof(room));
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<n;k++){
                    cin>>room[i][j][k];
                    if(room[i][j][k]=='X') vis[i][j][k]=-1;
                }
            }
        }
        cin>>y1>>z1>>x1;
        cin>>y2>>z2>>x2;
        cin>>s;
        BFS();
    }
    return 0;
}