https://vjudge.net/problem/HDU-1240
题意：在一个三维空间中找条路线，是否能到达终点。
多组数据输入
第一行 Start N (一个N*N*N的三维空间)
输入这个三维空间。
'X'表示不可走
'O'表示可走
输入起点和终点
注意起点和终点是(y,z,x)
啊啊啊 英语太烂了 没注意输入的起点和终点，误认为输入的起点和终点是 (x,y,z) wa了两发
题解：BFS 解这个 N*N*N 的空间，寻找解决方案。
#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int N = 12;
char mp[N][N][N];
char st[10],ed[10];
int n;
int dir[6][3] = {0,0,1,0,1,0,1,0,0,0,0,-1,0,-1,0,-1,0,0}; //方向
int sx,sy,sz,ex,ey,ez; //起点(x,y,z) 终点(x,y,z)
struct node //定义结构体
{
int x,y,z,step;
};
bool inbound(int x, int l, int r) //判断方向是否合法
{
if(x < l || x >= r) return false;
return true;
}
void bfs()
{
bool flag = true; //标记是否有路线
node now,Next;
now.step = 0, now.x = sx, now.y = sy, now.z = sz;
queue<node> q;
q.push(now); //入队
while(!q.empty())
{
now = q.front(); //获取当前队首
q.pop(); //出队
if(now.x == ex && now.y == ey && now.z == ez) //看是否到达终点
{
flag = false;
printf("%d %d
",n,now.step);
break;
}
for(int i = 0; i < 6; i++) //方向扩展
{
Next.x = now.x + dir[i][0];
Next.y = now.y + dir[i][1];
Next.z = now.z + dir[i][2];
if(!inbound(Next.x,0,n) || !inbound(Next.y,0,n) || !inbound(Next.z,0,n)) continue; //是否合法
if(mp[Next.x][Next.y][Next.z] == 'O') //是否可走
{
Next.step = now.step + 1;
mp[Next.x][Next.y][Next.z] = 'X';
q.push(Next);
}
}
}
if(flag) puts("NO ROUTE");
}
int main()
{
while(~scanf(" %s %d",st,&n))
{
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
scanf(" %c",&mp[i][j][k]);
scanf(" %d %d %d %d %d %d %s",&sy,&sz,&sx,&ey,&ez,&ex,ed);
bfs();
}
return 0;
}