Under construction

Still being built. Things may change

Asteroids!

Time limit1sMemory limit128 MB

Summary
Find the shortest 6-directional path through an N by N by N grid with blocked cells, or report that no route exists.
Level

Easy3 of 10

Topics
BFS, Matrix
Solved
No attempts yet

Problem

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

Input

The input holds at least one and at most 100 data sets. Each data set follows the format below, and no blank lines separate them.

A data set has five parts.

  1. Start line. One line, START N, with 1≤N≤101 \le N \le 10.
  2. Slice list. NN slices in order. Each slice is an N×NN \times N matrix cut horizontally through the asteroid field, one matrix row per line, so N×NN \times N lines in total. Every position holds one of two values.
    • O (the letter oh) empty space
    • X (upper case) an asteroid
  3. Starting position. One line, A B C, the coordinates ⟨A,B,C⟩\langle A, B, C \rangle your craft starts from. The three values are integers separated by single spaces.
  4. Target position. One line, D E F, the coordinates ⟨D,E,F⟩\langle D, E, F \rangle you have to reach. The three values are integers separated by single spaces.
  5. End line. One line, END. The last data set may leave this line out.

The origin of the coordinate system is ⟨0,0,0⟩\langle 0, 0, 0 \rangle, so every component of every coordinate is an integer between 00 and N−1N-1, inclusive.

  • The first value is the column. The left column is 00.
  • The second value is the row. The top row is 00.
  • The third value is the slice. The first slice is 00.

Both the starting position and the target position are empty space.

Output

Print one line for each data set, with no blank lines between the lines.

If a route exists, print two integers separated by a space. The first is the NN of that data set, the second is the least number of moves needed to get from the starting position to the target position. If no route exists, print NO ROUTE instead.

A move goes in one of the six basic directions: up, down, left, right, forward, back. Put precisely, a move increments or decrements a single component of your current position vector by 11. You cannot move into a cell that holds an asteroid, and you cannot leave the field.

Examples1

  1. Example 1

    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
    
    Expected output
    1 0
    3 4
    NO ROUTE