Asteroids是一道坐标点三维的bfs题目，尤其是在三维坐标的输入存储的过程中，需要注意。

\Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7201 Accepted Submission(s): 4454
**

Problem Description

You’re in space.
You want to get home.
There are asteroids.
You don’t want to hit them.

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 5 components:

Start line - A single line, “START N”, where 1 <= N <= 10.

Slice list - A series of N slices. Each slice is an N x N matrix representing a horizontal slice through the asteroid field. Each position in the matrix will be one of two values:

‘O’ - (the letter “oh”) Empty space

‘X’ - (upper-case) Asteroid present

Starting Position - A single line, “A B C”, denoting the coordinates of your craft’s starting position. The coordinate values will be integers separated by individual spaces.

Target Position - A single line, “D E F”, denoting the coordinates of your target’s position. The coordinate values will be integers separated by individual spaces.

End line - A single line, “END”

The origin of the coordinate system is <0,0,0>. Therefore, each component of each coordinate vector will be an integer between 0 and N-1, inclusive.

The first coordinate in a set indicates the column. Left column = 0.

The second coordinate in a set indicates the row. Top row = 0.

The third coordinate in a set indicates the slice. First slice = 0.

Both the Starting Position and the Target Position will be in empty space.

Output

For each data set, there will be exactly one output set, and there will be no blank lines separating output sets.

A single output set consists of a single line. If a route exists, the line will be in the format “X Y”, where X is the same as N from the corresponding input data set and Y is the least number of moves necessary to get your ship from the starting position to the target position. If there is no route from the starting position to the target position, the line will be “NO ROUTE” instead.

A move can only be in one of the six basic directions: up, down, left, right, forward, back. Phrased more precisely, a move will either increment or decrement a single component of your current position vector by 1.

Sample Input

START 1
O
0 0 0
0 0 0
END
START 3
XXX
XXX
XXX
OOO
OOO
OOO
XXX
XXX
XXX
0 0 1
2 2 1
END
START 5
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
XXXXX
XXXXX
XXXXX
XXXXX
XXXXX
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
0 0 0
4 4 4
END

Sample Output

1 0
3 4
NO ROUTE

Source

South Central USA 2001

poj2225 亦为此题

题意及要求

先来说说真实的题意吧：

题目给出一个三维的图，使得从一个三维的点，从起点到终点最短距离以及能否走到。多次输出题目。

看似是一道很简单的[[bfs]]题目，其实他就是一道很简单的bfs题目。

不信你看，本题目其中的bfs的内容就是这样正常。

while ((!q.empty()))
    {
        node front = q.front();
        q.pop();

        if((front.x== D)&&(front.y== E)&&(front.z== F)){
            cout<<n<<" "<<front.cnt<<endl;
            return;
        }
        front.cnt++;
        node next = front;
        for(int i=0;i<6;i++){
            next.x = front.x + move[i][0];
            next.y = front.y + move[i][1];
            next.z = front.z + move[i][2];
          //  cout<<"x,y,z is  "<<next.x<<" "<<next.y<<" "<<next.z<<"  val is "<<val[next.x][next.y][next.z]<<" CHECK is "<<CHECK(next.x,next.y,next.z)<<endl;
            if(CHECK(next.x,next.y,next.z)){
                vis[next.x][next.y][next.z]=1;
                q.push(next);
            }
        }
    }cout<<"NO ROUTE"<<endl;

但是

问题来了，这道题还是对我造成了很大的困扰的，因为在数据的输入和存储这一块吃了大亏。

第一次看完题目，感觉像是给出是一个坐标点，然后所给的数据分成了多层，层与层是可以互通的，就想着把他当作二维的来做。写的时候还感到奇怪，为什么有六种动作呢，不就是只有四种（前后左右）么？还沾沾自喜，感觉自己找到了捷径。。。。。。

后来吧，总是wa，看了别人的讨论才发现原来题看错了，理解错误（英语还需增强啊，太尬了~~~）

这个时候的心情再回首回去当时，就感觉当时的自己仿佛是低维空间的生物在理解着三维世界的神奇（并且是失败的那种），科幻的感觉啊啊。

接着在写正确的三维的版本的时候，仍是接连不断的错误喷涌而来，通过长久的层层的debug（数小时）发现是在输入和储存方面出现了错误，题目给定的是一个接着一个二维图数据，所以需要自己去转化，但是，当时自己只想到了第一层，把高度使用行号/n来判断，他的高度，但是忘记给行号更改了，导致自己出现了错误，许多点没有标记上。（属于坐标错误吧，矩阵储存失败。。。）

导致了本应很顺利的题目，搞了很久，另外，题目给定的顺序是 列 行，而不是行列，所有还需要自己翻一下。

// #include<bits/stdc++.h>
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
#define CLR(x,y) memset(x,y,sizeof(x))
#define CHECK(x,y,z) (x>=0&&x<n&&y>=0&&y<n&&z>=0&&z<n&&!(vis[x][y][z])&&val[x][y][z])
//val bug
struct node
{
    int x,y,z,cnt;
};


void bfs(int n){
    int move[6][3]={
    {1,0,0},
    {-1,0,0},
    {0,1,0},
    {0,-1,0},
    {0,0,1},
    {0,0,-1}
};
    bool vis[n][n][n];  
    bool val[n][n][n];
    CLR(vis,false);
    CLR(val,false);
    int A,B,C,D,E,F;
    char c;
    for(int i=0;i<n*n;i++){
        for(int j=0;j<n;j++){
                scanf("%c",&c);
                if(c == 'O')val[i%n][j][i/n]=1;
        }
        getchar();
    }
    
    scanf("%d %d %d %d %d %d\n", &B,&A,&C,&E,&D,&F);
    scanf("END\n");
    queue<node> q;
    node t;
    t.x = A;t.y= B;t.z =C;t.cnt=0;
    q.push(t);
    vis[A][B][C]=1;
    while ((!q.empty()))
    {
        node front = q.front();
        q.pop();

        if((front.x== D)&&(front.y== E)&&(front.z== F)){
            cout<<n<<" "<<front.cnt<<endl;
            return;
        }
        front.cnt++;
        node next = front;
        for(int i=0;i<6;i++){
            next.x = front.x + move[i][0];
            next.y = front.y + move[i][1];
            next.z = front.z + move[i][2];
            if(CHECK(next.x,next.y,next.z)){
                vis[next.x][next.y][next.z]=1;
                q.push(next);
            }
        }
    }cout<<"NO ROUTE"<<endl;
    return ;
}

int main(){
    int n;
    while(~scanf("START %d\n",&n)){
        bfs(n);
    }

    return 0;
}