P9909 [COCI 2023/2024 #2] Pingvin

Given an $n \times n \times n$ cube, it is divided into $n^3$ unit cubes, and some of the unit cubes are obstacles and cannot be passed through. Given the coordinates of the start and the target, in each step you can move from one unit cube to an adjacent (sharing a face) non-obstacle unit cube. Find the minimum number of steps needed to go from the start to the target.

The first line contains an integer $n$. The next line contains $3$ integers $x_s, y_s, z_s$, representing the starting position. The next line contains $3$ integers $x_t, y_t, z_t$, representing the target position. Then $n$ $n \times n$ $01$ matrices are given. In the $i$-th layer, the cell in row $j$ and column $k$ indicates whether $(j, k, i)$ is an obstacle ($1$ means obstacle). It is guaranteed that the start and the target positions are not obstacles.

Output one integer in a single line, representing the minimum number of steps. If it is impossible to reach, output $-1$.

### Constraints |$\text{Subtask}$|Score|Special Property| |:-:|:-:|:-:| |$1$|$7$|$n = 2$| |$2$|$16$|No obstacles| |$3$|$22$|All cells with $z$ coordinate greater than $1$ are obstacles| |$4$|$25$|None| For all testdata, $1 \le n \le 100$. Translated by ChatGPT 5