Rescue Robot in the Derelict Spaceship

A lone robot is trapped among the scattered wreckage of an abandoned spaceship. Somewhere inside the wreck is a teleporter that can save the robot by transporting it to safety. However, the spaceship is tumbling uncontrollably in space with artificial gravity always pulling the robot away from a nearby star. The star’s light, coming from above, illuminates only those parts of the wreck that are not blocked by debris in the upward direction.

The spaceship and its surrounding area are represented by a three-dimensional grid of size \(m \times n \times p\). Each cell in the grid is either part of the debris (denoted by a '#' character) or vacuum (denoted by a '.' character). Note that the debris may form disconnected parts.

The robot starts fixed on a debris cell, and it can choose when to move or wait for the light to be right. However, it can move only when the cell it is attached to is illuminated. A cell at coordinates \((r, c, h)\) is considered illuminated if there is no debris in any cell directly above it; formally, for all levels \(l\) with \(h < l < p\), the cell \((r, c, l)\) is vacuum.

The available moves are as follows (assume that the upward direction is the direction from which light comes):

1. Flat Move: If the robot is fixed on a debris cell, it may move horizontally (north, south, east or west) to an adjacent cell on the same level. The destination cell must also be debris and illuminated. Diagonal moves are not allowed.
2. Jump Down: Standing on a debris cell, the robot may step off toward an adjacent cell that is not debris on the same level. Once it steps off, it will fall downward (i.e. toward lower levels) until it lands on a debris cell. There is no restriction on the falling height, but the landing cell must be illuminated and within the grid (falling into void is not allowed).
3. Falling: If the robot finds itself suspended in air (not on a debris cell) yet illuminated, it may drop downward until landing on debris. (This often occurs after a jump down; note that the teleporter only works if the robot lands and fixes itself on a debris cell after a move. Passing through the teleporter cell while falling does not count.)

The robot's goal is to reach the teleporter, which is located on a debris cell. Among all possible valid ways to reach the teleporter, the robot wishes to minimize the number of moves (each flat move, jump down, or fall counts as one move).

Input Format

The input begins with a line containing three integers\(m\), \(n\), and \(p\), representing the number of rows, columns, and levels (vertical layers) of the grid respectively. The rows are indexed from 0 to \(m-1\), the columns from 0 to \(n-1\), and the levels from 0 to \(p-1\) (with level \(p-1\) being the top layer where light always reaches).

The second line contains three integers: \(s_r\), \(s_c\), and \(s_h\), representing the starting coordinates of the robot. The third line contains three integers: \(t_r\), \(t_c\), and \(t_h\), representing the teleporter's coordinates.

This is followed by \(p\) blocks. Each block describes one level of the grid starting from level 0 (the bottom) up to level \(p-1\) (the top). Each level consists of \(m\) lines, and each line contains exactly \(n\) characters which are either '#' or '.'.

Output Format

Output a single integer representing the minimum number of moves required for the robot to reach the teleporter. If it is impossible for the robot to reach the teleporter under the conditions, output -1.

Illumination Details

A cell \((r, c, h)\) is illuminated if for every level \(l\) with \(h < l < p\), the cell \((r, c, l)\) is a vacuum (i.e. contains a '.'). Note that cells on the top level (level \(p-1\)) are always illuminated.

Sample Test Cases

Test Case 1 (Score: 30)

3 3 3
1 1 2
1 1 0
###
##.  
###
###
##.  
###
###
##.  
###

Explanation: In this test case, the grid is 3×3×3. The top (level 2) has a gap at position (1,2,2) allowing the robot to jump down. The robot can jump from (1,1,2) to (1,2,0) in one move and then perform a flat move to reach (1,1,0) – a total of 2 moves.

Test Case 2 (Score: 40)

3 3 3
0 0 2
2 2 0
##.
###
###
##.
###
###
###
###
###

Explanation: The robot must combine flat moves with a jump down maneuver. One possible sequence is: flat move from (0,0,2) to (0,1,2), jump down from (0,1,2) to (0,2,0), and then two flat moves from (0,2,0) to (2,2,0), totaling 4 moves.

Test Case 3 (Score: 30)

2 2 2
0 0 1
1 1 0
##
##
#.
.#

Explanation: Although the starting cell is illuminated, the teleporter cell (1,1,0) is not illuminated (blocked by debris above). Therefore, no valid sequence of moves exists, and the output is -1.

inputFormat

The first line contains three integers \(m\), \(n\), and \(p\). The second line contains the starting coordinates \(s_r\), \(s_c\), \(s_h\). The third line contains the teleporter coordinates \(t_r\), \(t_c\), \(t_h\). This is followed by \(p\) blocks, each consisting of \(m\) lines with exactly \(n\) characters (each either '#' or '.'). The blocks are given in order from level 0 (bottom) to level \(p-1\) (top).

outputFormat

Output a single integer – the minimum number of moves required to reach the teleporter, or -1 if it is impossible.

sample

3 3 3
1 1 2
1 1 0
###
##.
###
###
##.
###
###
##.
###

2