209

# 题目

## 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 <A,B,C> 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 <D,E,F> 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.

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

1 0
3 4
NO ROUTE

# 代码

/*By:OhYeeGithub:OhYeeEmail:oyohyee@oyohyee.comBlog:http://www.cnblogs.com/ohyee/かしこいかわいい？エリーチカ！要写出来Хорошо的代码哦~*/#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <vector>#include <list>#include <queue>#include <stack>#include <map>using namespace std;//DEBUG MODE#define debug 0//循环#define REP(n) for(int o=0;o<n;o++)const int maxn = 11;int n;int dis[maxn][maxn][maxn];char Map[maxn][maxn][maxn];const int delta[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};struct point {    int x,y,z;    point() {        x = y = z = -1;    }    point(int a,int b,int c) {        x = a;        y = b;        z = c;    }    bool operator == (const point &rhs)const {        return ((x == rhs.x) && (y == rhs.y) && (z == rhs.z));    }};inline int read_int() {    char c;    int ans = 0;    while (c = getchar(),!(c >= '0' && c <= '9'));    while (c >= '0'&&c <= '9') {        ans *= 10;        ans += (int)c - '0';        c = getchar();    }    return ans;}int BFS(point s,point v) {    if (s == v)        return 0;    memset(dis,-1,sizeof(dis));    queue<point> Q;    Q.push(s);    dis[s.x][s.y][s.z] = 0;    while (!Q.empty()) {        int x = Q.front().x;        int y = Q.front().y;        int z = Q.front().z;        Q.pop();        REP(6) {            int xx = x + delta[o][0];            int yy = y + delta[o][1];            int zz = z + delta[o][2];            //非法路径            if (xx < 0 || xx >= n || yy < 0 || yy >= n || zz < 0 || zz >= n)                continue;            //墙            if (Map[xx][yy][zz] == 'X')                continue;            //尚未访问过            if (dis[xx][yy][zz] == -1) {                dis[xx][yy][zz] = dis[x][y][z] + 1;                //到达终点                if (point(xx,yy,zz) == v)                    return dis[xx][yy][zz];                Q.push(point(xx,yy,zz));            }        }    }    return -1;}bool Do() {    char c;    if (scanf("\n%c",&c) == EOF)        return false;    n = read_int();    //printf(" (%d) \n",n);    for (int k = 0;k < n;k++)//块        for (int i = 0;i < n;i++)//行                scanf("%s",Map[k][i]);    int s1,s2,s3,v1,v2,v3;    s1 = read_int();    s2 = read_int();    s3 = read_int();    v1 = read_int();    v2 = read_int();    v3 = read_int();    //scanf("%d%d%d",&s1,&s2,&s3);    //scanf("%d%d%d",&v1,&v2,&v3);    point s = point(s3,s1,s2);    point v = point(v3,v1,v2);        int ans = BFS(s,v);    if (ans == -1)        printf("NO ROUTE\n");    else        printf("%d %d\n",n,ans);    scanf("%*s");    return true;}int main() {    while (Do());    return 0;}

• 点击查看/关闭被识别为广告的评论