hdu1240 参考答案

返回“大学生程序设计竞赛”

/*
zju 1438  hdu 1240 经典：三维BFS
ymc 2008/9/16
题目大意：
三维迷宫问题:注意输入是x，y，z的顺序。
解题思路：
BFS搜索
*/
#include <iostream>
#include <string>
#include <queue>
using namespace std;
const int N=11;
char graph[N][N][N];
int dist[N][N][N];
int n;
int sx,sy,sz,ex,ey,ez;
int step[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
void BFS()
{
    memset(dist,255,sizeof(dist));
    dist[sx][sy][sz]=0;
    int x,y,z;
    int x1,y1,z1;
    queue<int> q;
    q.push(sx); q.push(sy); q.push(sz);
    while(!q.empty())
    {
        x=q.front();q.pop();
        y=q.front();q.pop();
        z=q.front();q.pop();
        if(x==ex&&y==ey&&z==ez)
            return ;
        for(int i=0;i<6;i++)
        {
            x1=x+step[i][0];
            y1=y+step[i][1];
            z1=z+step[i][2];
            if(x1<0||x1>=n||y1<0||y1>=n||z1<0||z1>=n)
                continue;
            if(graph[x1][y1][z1]=='X'||dist[x1][y1][z1]>=0)
                continue;
            dist[x1][y1][z1]=dist[x][y][z]+1;
            q.push(x1);q.push(y1);q.push(z1);
        }
    }
}
int main()
{
    string s;
    while(cin>>s)
    {
        cin>>n;
        for(int z=0;z<n;z++)
            for(int y=0;y<n;y++)
                for(int x=0;x<n;x++)
                    cin>>graph[x][y][z];
        cin>>sx>>sy>>sz>>ex>>ey>>ez;
        cin>>s;
        BFS();
        if(dist[ex][ey][ez]<0)
            cout<<"NO ROUTE"<<endl;
        else
            cout<<n<<' '<<dist[ex][ey][ez]<<endl;
    }
}