Asteroids!
Time limit1sMemory limit128 MB
Find the shortest 6-directional path through an N by N by N grid with blocked cells, or report that no route exists.
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.
- Start line. One line,
START N, with . - Slice list. slices in order. Each slice is an matrix cut horizontally through the asteroid field, one matrix row per line, so lines in total. Every position holds one of two values.
O(the letter oh) empty spaceX(upper case) an asteroid
- Starting position. One line,
A B C, the coordinates your craft starts from. The three values are integers separated by single spaces. - Target position. One line,
D E F, the coordinates you have to reach. The three values are integers separated by single spaces. - End line. One line,
END. The last data set may leave this line out.
The origin of the coordinate system is , so every component of every coordinate is an integer between and , inclusive.
- The first value is the column. The left column is .
- The second value is the row. The top row is .
- The third value is the slice. The first slice is .
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 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 . You cannot move into a cell that holds an asteroid, and you cannot leave the field.