[数据结构与算法]hdu1240题解与思考 Asteroids!

hdu1240题解与思考 Asteroids!

1. 题意：
   简单说就是走一个三维的迷宫

2. 思路：
   解决迷宫的思路当然就是队列+bfs啦，三位迷宫只要注意改一下检测数组vis为三位数组就可以了，当然这个题目也有一个坑点：输入迷宫时不是按照我们的惯性思维先行后列再层，要结合题意。当然也有一些格式方面的要注意。

3. 代码奉上：

#include<iostream>
#include<queue>
#include<string>
using namespace std;

struct node {
	int x;
	int y;
	int z;
	int step;
};
//node operate[6] = {
//	{0,0,1},	//上
//	{0,0,-1},	//下
//	{0,-1,0},	//左
//	{0,1,0},	//右
//	{1,0,0},	//前
//	{-1,0,0}	//后
//};
bool vis[100][100][100];
char a[100][100][100];
int n;

bool CHECK(int x, int y, int z) { return x > -1 && x<n&& y>-1 && y < n&& z>-1 && z < n; }
void Way(int dx,int dy,int dz,int tx,int ty,int tz) {
	node orign;
	orign.x = dx;
	orign.y = dy;
	orign.z = dz;
	orign.step = 0;
	queue<node> q;
	q.push(orign);
	while (!q.empty()) {
		node front = q.front();
		node next;
		if (front.x == tx && front.y == ty && front.z == tz) {
			cout << n<<" "<<front.step << endl;
			return;
		}
		for (int i = 0; i < 6; i++) {
			if (i == 0) {
				next.x = front.x + 0;
				next.y = front.y + 0;
				next.z = front.z + 1;
				if (CHECK(next.x,next.y,next.z)&&!vis[next.x][next.y][next.z] && a[next.x][next.y][next.z] != 'X') {
					next.step = front.step + 1;
					q.push(next);
					vis[next.x][next.y][next.z] = true;
				}
			}
			if (i == 1) {
				next.x = front.x + 0;
				next.y = front.y + 0;
				next.z = front.z - 1;
				if (CHECK(next.x, next.y, next.z) && !vis[next.x][next.y][next.z] && a[next.x][next.y][next.z] != 'X') {
					next.step = front.step + 1;
					q.push(next);
					vis[next.x][next.y][next.z] = true;
				}
			}
			if (i == 2) {
				next.x = front.x + 0;
				next.y = front.y - 1;
				next.z = front.z + 0;
				if (CHECK(next.x, next.y, next.z) && !vis[next.x][next.y][next.z] && a[next.x][next.y][next.z] != 'X') {
					next.step = front.step + 1;
					q.push(next);
					vis[next.x][next.y][next.z] = true;
				}
			}
			if (i == 3) {
				next.x = front.x + 0;
				next.y = front.y + 1;
				next.z = front.z + 0;
				if (CHECK(next.x, next.y, next.z) && !vis[next.x][next.y][next.z] && a[next.x][next.y][next.z] != 'X') {
					next.step = front.step + 1;
					q.push(next);
					vis[next.x][next.y][next.z] = true;
				}
			}
			if (i == 4) {
				next.x = front.x + 1;
				next.y = front.y + 0;
				next.z = front.z + 0;
				if (CHECK(next.x, next.y, next.z) && !vis[next.x][next.y][next.z] && a[next.x][next.y][next.z] != 'X') {
					next.step = front.step + 1;
					q.push(next);
					vis[next.x][next.y][next.z] = true;
				}
			}
			if (i == 5) {
				next.x = front.x - 1;
				next.y = front.y + 0;
				next.z = front.z + 0;
				if (CHECK(next.x, next.y, next.z) && !vis[next.x][next.y][next.z] && a[next.x][next.y][next.z] != 'X') {
					next.step = front.step + 1;
					q.push(next);
					vis[next.x][next.y][next.z] = true;
				}
			}
		}
		q.pop();
	}
	cout << "NO ROUTE" << endl;
}

int main() {
	int dx, dy, dz,tx,ty,tz;
	string s1, s2;
	while (cin >>s1>> n) {
		memset(vis, false, sizeof(vis));
	    for(int k = 0; k < n; k++) {	//注意此处根据题意（样例），要把每行每列输完再每层
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n;j++) {
					cin >> a[i][j][k];
				}
			}
		}
		cin >> dx >> dy >> dz;
		cin >> tx >> ty >> tz;
		cin >> s2;
		Way(dx, dy, dz, tx, ty, tz);
	}
	return 0;
}

AC!