【BFS】hdu 1240 Asteroids!
题目描述：
http://acm.hdu.edu.cn/showproblem.php?pid=1240
中文大意：
人在太空，想要回家，遇小行星，需要绕行。
行星场的大小为 N x N x N，飞行器可以在上、下、左、右、前、后 6 个方向上移动，但仅限标记为 “O” 的区域，标记为 “X” 的区域代表有行星。
要求：计算回家的最少移动次数，若不能回家，打印 “NO ROUTE”。
思路：
（1）如果起点和终点在同一个位置，则返回 0 ，过程结束，否则执行接下来的操作；
（2）设置起点 s 的移动次数为 0 ，并将其放到队列 q 中；
（3）如果 q 是空队列，则说明整个 bfs 过程并没有找到终点，返回 -1，过程结束，否则继续；
（4）取队列 q 中最前面的节点 node；
（5）尝试访问 node 节点周围的节点（注意是 6 个方向），若没有后继节点，即周围都是行星，则转到（3）；
（6）将 node 节点的所有后继节点的移动次数设置为 node.dis + 1，并标记为不可再被访问；
（7）如果后继节点中存在终点，则返回其移动次数，过程结束，否则将所有后继节点都放在队列 q 的末端；
（8）转到（3）。
代码：
#include<bits/stdc++.h>
using namespace std;
char star[10][10][10];
int n;
struct node{
int x,y,h;
int dis;
};
int dir[6][3] = {{0,0,1}, {0,0,-1}, {0,1,0}, {0,-1,0}, {1,0,0}, {-1,0,0}};
node start,goal;
bool check(node next){
if(next.x >=0 && next.x < n && next.y >=0 && next.y < n && next.h >=0 && next.h < n){
return true;
}
return false;
}
int bfs(){
if(start.h == goal.h && start.y == goal.y && start.x == goal.x){
return 0;
}
start.dis = 0;
queue<node> q;
q.push(start);
while(!q.empty()){
start = q.front();
q.pop();
for(int i=0;i<6;i++){
node next;
next.x = start.x + dir[i][0];
next.y = start.y + dir[i][1];
next.h = start.h + dir[i][2];
if(check(next) && star[next.h][next.y][next.x] == 'O'){
star[next.h][next.y][next.x] = 'X';
next.dis = start.dis + 1;
if(next.h == goal.h && next.y == goal.y && next.x == goal.x){
return next.dis;
}
q.push(next);
}
}
}
return -1;
}
int main(){
string str;
while(cin>>str){
scanf("%d", &n);
getchar();
for(int i=0;i<n;i++){//slice
for(int j=0;j<n;j++){//row
for(int k=0;k<n;k++){//column
scanf("%c", &star[i][j][k]);
}
getchar();
}
}
scanf("%d %d %d", &start.x, &start.y, &start.h);
scanf("%d %d %d", &goal.x, &goal.y, &goal.h);
cin>>str;
int num = bfs();
if(num == -1){
printf("NO ROUTE
");
}
else{
printf("%d %d
", n, num);
}
}
}