pingvin — COCI CONTEST_#2
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 9
Algorithms: shortest path, grid traversal, bfs, 3d geometry

# Task Pingvin
Zrakoplović the penguin wants to learn how to fly!

The space in which he will learn to fly can be imagined as a cube of dimensions $n \times n \times n$, divided into $n^3$ unit cubes. Each unit cube can be described with three coordinates ($x, y, z$), where $x$, $y$ and $z$ are integers between 1 and $n$. The coordinate $x$ denotes the distance from the left edge of the space, the coordinate $y$ denotes the distance from the front edge of the space, and the coordinate $z$ denotes the height.

![](_page_0_Picture_5.jpeg)

Some of these unit cubes contain clouds, and some do not.

Zrakoplović is afraid of clouds, so he will learn to fly only where there are no clouds. He initially finds himself at a position ($x_s, y_s, z_s$), such that $z_s$ = 1 (i.e. at height 1), and wants to get to position ($x_e, y_e, z_e$).

At the moment, he is perfecting the skill of flying in directions that are parallel to one of the axes of space (i.e. in the direction of the $x$-axis, $y$-axis or $z$-axis), and in one wing flap he can cross at most one unit cube.

Before he decides to fly, Zrakoplović wants to know how many wing flaps he needs to get to the desired position. While he is preparing for the flight, help him answer that question.

## Input

The first line contains an integer *n* (1 $\le$ *n* $\le$ 100), the dimension of the space in which Zrakoplović learns to fly.

The second line contains three integers $x_s$, $y_s$ and $z_s$ (1 $\le$ $x_s, y_s$ $\le$ *n*, $z_s$ = 1), the start position of Zrakoplović.

The third line contains three integers $x_e$, $y_e$ and $z_e$ (1 $\le$ $x_e, y_e, z_e$ $\le$ *n*), the end position of Zrakoplović.

This is followed by *n* binary matrices of dimensions $n \times n$ that describe the space, where the *i*-th matrix describes the space at height *i*. The upper-left corner has the coordinates (1, 1, *i*). The row and column of the matrix correspond to the *x* and *y* coordinates, respectively.

'0' denotes a unit cube in which there are no clouds, and '1' denotes a unit cube in which there are clouds.

The start and end position of Zrakoplović will not be a cloud.

## Output

In the first and only line, print the smallest number of wing flaps that Zrakoplović must make to reach the desired position. If Zrakoplović cannot reach the desired position, print '-1'.

#### Scoring

| Subtask | Points | Constraints                                                    |
|---------|--------|----------------------------------------------------------------|
| 1       | 7      | $n = 2$                                                          |
| 2       | 16     | There are no clouds.                                           |
| 3       | 22     | All positions with z-coordinate greater than 1 will be clouds. |
| 4       | 25     | No additional constraints.                                     |

# Examples

| input  | input  | input  |
|--------|--------|--------|
| 2      | 3      | 3      |
| 1 1 1  | 2 3 1  | 2 1 1  |
| 1 1 2  | 1 1 1  | 3 2 2  |
| 00     | 000    | 000    |
| 10     | 010    | 010    |
| 01     | 000    | 110    |
| 00     | 111    | 010    |
|        | 111    | 001    |
|        | 111    | 001    |
|        | 111    | 101    |
|        | 111    | 110    |
|        | 111    | 000    |
| output | output | output |
| 1      | 3      | 3      |

#### Clarification of the first example:

Zrakoplović can reach the desired position in one wing flap by moving in the direction of the *z*-axis for one unit cube.

#### Clarification of the third example:

Zrakoplović can reach the desired position in three wing flaps by first moving to position (2, 1, 2), then to (2, 2, 2) and finally to (3, 2, 2).

Starter code: