17114번 - 하이퍼 토마토

시프트의 토마토 농장은 아래 그림과 같이 토마토를 보관하는 큰 11차원 창고를 가지고 있다. 창고는 m × n × o × p × q × r × s × t × u × v × w 의 격자 모양이고, 각 칸에 토마토를 하나씩 보관할 수 있다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 $\begin{bmatrix} \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0\\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \end{bmatrix}$의 스물 두 방향에 인접해 있는 토마토를 의미한다. 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 시프트는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

m, n, o, p, q, r, s, t, u, v, w 와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 창고의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

첫 줄에는 문제의 설명에서 창고의 크기를 나타내는 자연수 m, n, o, p, q, r, s, t, u, v, w가 주어진다. 단, 1 ≤ mnopqrstuvw ≤ 10⁶ 이다.

둘째 줄부터는 창고에 저장된 토마토들의 정보가 주어진다. 창고 안의 격자 공간을 (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)부터 (m, n, o, p, q, r, s, t, u, v, w)까지의 좌표로 나타낸다고 하면,

• 둘째 줄에는 (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)부터 (m, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)까지에 들어 있는 토마토 m개의 정보가 주어지고,
• 이러한 줄이 n번 반복되어  (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)부터 (m, n, 1, 1, 1, 1, 1, 1, 1, 1, 1)까지에 들어 있는 토마토 mn개의 정보가 주어지고,
• 이러한 n개의 줄이 o번 반복되어 (m, n, o, 1, 1, 1, 1, 1, 1, 1, 1)까지에 들어 있는 토마토 mno개의 정보가 주어지고,
• 이러한 no개의 줄이 p번 반복되어 (m, n, o, p, 1, 1, 1, 1, 1, 1, 1)까지에 들어 있는 토마토 mnop개의 정보가 주어지고,
• ⋯ 이와 같은 방법으로 nopqrstuvw개의 줄에 걸쳐 (m, n, o, p, q, r, s, t, u, v, w)까지에 들어 있는 토마토 mnopqrstuvw개의 정보가 모두 주어진다.

정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해 출력한다. 만약 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.