首页 > 代码库 > hdu 1240 Asteroids!

hdu 1240 Asteroids!

     题目大意:给出每一层的路况,‘O‘表示这路是可以走的,‘X‘表示此路不通,程序结果要求输出四方体的维数(已经给出)和起点到达终点所需的最小步数。

    第二组数据

   

START 3
XXX //最下面一层
XXX
XXX
OOO //中间一层
OOO
OOO
XXX //最上面一层
XXX
XXX
0 0 1
2 2 1
END


       


#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 15
struct Node
{
    int x, y, z;
    int num;
    Node(int x, int y, int z, int num):x(x),y(y),z(z), num(num){}
    Node(){}
};
char n[MAX][MAX][MAX];
Node s, e;
int v[MAX][MAX][MAX], flag;
int dx[]={0,0,1,-1,0,0};
int dy[]={0,0,0,0,1,-1};
int dz[]={1,-1,0,0,0,0};
int main()
{
    int N, x, y, z, i;
    char str[10], c;
    while (cin>>str>>N)
    {
       flag = 0;
       memset(v, 0, sizeof(v));
	   for (z=1; z<=N; z++)
       for (x=1; x<=N; x++)
          for (y=1; y<=N; y++)
            
              cin>>n[x][y][z];
        cin>>s.x>>s.y>>s.z;
        cin>>e.x>>e.y>>e.z;
        cin>>str;
        queue<Node> q;
        v[s.x+1][s.y+1][s.z+1] = 1;
        q.push(Node(s.x+1,s.y+1,s.z+1,0));
        while (!q.empty())
        {
            Node tmp = q.front();
            q.pop();
            if (tmp.x==e.x+1&&tmp.y==e.y+1&&tmp.z==e.z+1)
            {
                flag = 1;
                cout<<N<<" "<<tmp.num<<endl;
				break;
            }
            v[tmp.x][tmp.y][tmp.z] = 1;
            for (i=0; i<6; i++)
            {
             if (v[tmp.x+dx[i]][tmp.y+dy[i]][tmp.z+dz[i]] == 0 && n[tmp.x+dx[i]][tmp.y+dy[i]][tmp.z+dz[i]]=='O')
                {
                    q.push(Node(tmp.x+dx[i],tmp.y+dy[i],tmp.z+dz[i], tmp.num+1));
                }
            }
        }
        if (flag==0)
            cout<<"NO ROUTE"<<endl;
    }
    return 0;
}