HDU 1240 Asteroids!

时间:2022-02-04 01:56:53

三维广搜

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std; struct node
{
int x,y,z;
int steps;
}start,end,next;
int dx[]={,,,,,-};
int dy[]={,,-,,,};
int dz[]={,-,,,,};
char maps[][][];
int n,res; bool check(node &a)
{
if(a.x>=&&a.x<n&&a.y>=&&a.y<n&&a.z>=&&a.z<n)
return true;
else return false;
} int bfs()
{
if(start.x==end.x&&start.y==end.y&&start.z==end.z)
return res;
node cur;
queue<node> q;
while(!q.empty())
q.pop();
q.push(start);
maps[start.x][start.y][start.z]='X';
while(!q.empty())
{
cur=q.front();
q.pop();
for(int i=;i<;i++)
{
next.x=cur.x+dx[i];
next.y=cur.y+dy[i];
next.z=cur.z+dz[i];
if(next.x==end.x&&next.y==end.y&&next.z==end.z)
return cur.steps+;
if(maps[next.x][next.y][next.z]=='O'&&check(next))
{
next.steps=cur.steps+;
maps[next.x][next.y][next.z]='X';
q.push(next);
}
}
}
return -;
} int main()
{
int i,j;
char st[],ed[];
while(scanf("%s%d",&st,&n)!=EOF)
{
getchar();
for(i=;i<n;i++)
{
for(j=;j<n;j++)
scanf("%s",maps[i][j]);
getchar();
}
scanf("%d%d%d",&start.x,&start.y,&start.z);
scanf("%d%d%d",&end.x,&end.y,&end.z);
getchar();
gets(ed);
res=;
start.steps=;
res=bfs();
if(res>=) printf("%d %d\n",n,res);
else printf("NO ROUTE\n");
}
return ;
}