《算法競賽從入門到進階》心得及相關題解021--bfs--hdu1240

題目意思：hdu1240，n*n的立方體，O代表路，X代表障礙物，問從起點到終點至少需要多少步，如沒有路則輸出NO ROUTE。 解題思路：水題，bfs，連坑都沒有。 代碼明細：

//probID: hdu1240
//author: WiselyQY
//date: 2021-01-05
#include <bits/stdc++.h>
using namespace std;

const int INF=1<<30;
struct Node
{
    int x,y,z,step;
};
int n,vis[15][15][15],ans;
int sx,sy,sz, ex,ey,ez;
char g[15][15][15];
queue<Node> q;
const int dx[]={1,0,-1,0,0,0}, dy[]={0,1,0,-1,0,0}, dz[]={0,0,0,0,1,-1};
int in(int z, int x, int y)
{
    return z>=0 && z<n && x>=0 && x<n && y>=0 && y<n;
}
void bfs()
{
    Node u;
    u.x=sx; u.y=sy; u.z=sz; u.step=0;
    memset(vis,0,sizeof(vis));
    vis[u.z][u.x][u.y]=1;
    while(!q.empty()) q.pop();
    q.push(u);
    while(!q.empty())
    {
        u=q.front(); q.pop();
        int x=u.x, y=u.y, z=u.z, step=u.step;
        if(x==ex && y==ey && z==ez) {ans=step; return;}
        for(int i=0; i<6; i++)
        {
            int nx=x+dx[i], ny=y+dy[i], nz=z+dz[i];
            if(in(nz,nx,ny) && !vis[nz][nx][ny] && g[nz][nx][ny]=='O')
            {
                vis[nz][nx][ny]=1;
                Node nu;
                nu.x=nx; nu.y=ny; nu.z=nz; nu.step=step+1;
                q.push(nu);
            }
        }
    }
}
int main()
{
    clock_t start,end;
    start=clock();
#ifndef ONLINE_JUDGE
    freopen(R"(D:\hdu\1240_2\in.txt)","r",stdin);
#endif
    string str;
    while(cin>>str>>n)
    {
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                for(int k=0; k<n; k++)
                    cin>>g[i][j][k];
        cin>>sy>>sx>>sz>>ey>>ex>>ez>>str;
        ans=INF;
        bfs();
        if(ans==INF) cout<<"NO ROUTE"<<endl;
        else cout<<n<<" "<<ans<<endl;
    }
    end=clock();
    //printf("time=%lfs\n",(double)(end-start)/1000);
    return 0;
}