HDU 1240 (简单三维广搜) Asteroids!

给出一个三维的迷宫以及起点和终点,求能否到大终点,若果能输出最短步数

三维的问题无非就是变成了6个搜索方向

最后强调一下xyz的顺序,从输入数据来看,读入的顺序是map[z][x][y]

总之,这是很基础的一道题

 //#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std; struct Point
{
char type;
int x, y, z;
int steps;
}start, end; char map[][][];
int dir[][] = {{,,}, {-,,}, {,,}, {,-,}, {,,}, {,,-}};
char buff[];
int n; bool islegal(int x, int y, int z)
{
return (x>= && x<n && y>= && y<n && z>= && z<n && map[z][x][y]!='X');
} void BFS(void)
{
queue<Point> qu;
start.steps = ;
qu.push(start);
while(!qu.empty())
{
Point now = qu.front();
if(now.x==end.x && now.y==end.y && now.z==end.z)
{
printf("%d %d\n", n, now.steps);
return;
}
for(int i = ; i < ; ++i)
{
int xx = now.x + dir[i][];
int yy = now.y + dir[i][];
int zz = now.z + dir[i][];
if(islegal(xx, yy, zz))
{
Point next;
next.x = xx, next.y = yy, next.z = zz, next.steps = now.steps + ;
map[zz][xx][yy] = 'X';
qu.push(next);
}
}
qu.pop();
}
printf("NO ROUTE\n");
} int main(void)
{
#ifdef LOCAL
freopen("1240in.txt", "r", stdin);
#endif while(cin >> buff >> n)
{
for(int i = ; i < n; ++i)
for(int j = ; j < n; ++j)
cin >> map[i][j]; cin >> start.x >> start.y >> start.z;
cin >> end.x >> end.y >> end.z;
cin >> buff;
BFS();
}
return ;
}

代码君

上一篇:ccc 模拟重力


下一篇:创建型模式(过渡模式) 简单工厂模式(Simple Factory)