HDU解题报告——1240

  三维走迷宫，起点和终点可以在星球上，可以用一个大一些的数组保存迷宫，并把迷宫周围全部赋值为‘X’，利于接下来判断，mark数组保存到达结点的步数，初始化为0，因为起点为0，所以讲map中起点赋值‘X’，为了便于比较，再将map中终点赋值‘O’，这样只需要判断mark中终点的值即可,代码如下：

#include <iostream>
#include <cstring>
#include <queue>
#include <string>
using namespace std;
typedef struct point{
	int x,y,z;
}pi;
char map[12][12][12];
int mark[12][12][12],dir[6][3]={-1,0,0,1,0,0,0,-1,0,0,1,0,0,0,-1,0,0,1};
int sx,sy,sz,fx,fy,fz;
int bfs(int n)
{
	pi t;
	t.x=sx;t.y=sy;t.z=sz;
	queue<pi> p;
	p.push(t);
	map[fx][fy][fz]='O';
	map[sx][sy][sz]='X';
	while(!p.empty()){
		int x=p.front().x,y=p.front().y,z=p.front().z;
		for(int i=0;i<6;i++){
			int tx=x+dir[i][0],ty=y+dir[i][1],tz=z+dir[i][2];
			if(map[tx][ty][tz]=='X'||mark[tx][ty][tz]!=0) continue;
			mark[tx][ty][tz]=mark[x][y][z]+1;
			t.x=tx;t.y=ty;t.z=tz;
			p.push(t);
		}
		p.pop();
		if(mark[fx][fy][fz]!=0) return mark[fx][fy][fz];
	}
	return -1;
}
int main()
{
	string laji;
	int n;
	while(cin>>laji>>n){
		memset(mark,0,sizeof(mark));
		memset(map,'X',sizeof(map));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				for(int k=1;k<=n;k++) cin>>map[i][j][k];
		cin>>sx>>sy>>sz>>fx>>fy>>fz;
		cin>>laji;
		if(sx==fx&&sy==fy&&sz==fz) {cout<<n<<" 0\n";continue;}
		sx++;sy++;sz++;fx++;fy++;fz++;
		int r=bfs(n);
		if(r==-1) cout<<"NO ROUTE"<<endl;
		else cout<<n<<" "<<r<<endl;
	}
	return 0;
}