페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6035

비행 연습 1초 512MB

문제

남극의 펭귄, 팽수의 꿈은 하늘을 나는 것이다.

그 꿈을 이루기 위해 팽수는 최신 VR기기인 치타퀘스트3를 이용하여 비행 연습을 하고 있다.

VR 세계는 n \times n \times n 의 큐브 공간으로 이루어져 있으며 n^3개의 단위 큐브로 이루어져 있다. 또한 (x,y,z)의 좌표 값으로 위치를 나타낼 수 있으며 x,y,z는 각각 1과 n 사이의 정수이다.

  • x 좌표는 왼쪽 끝로부터의 거리

  • y 좌표는 앞쪽 끝으로부터의 거리

  • z 좌표는 높이를 나타낸다.

일부 단위 큐브 공간은 구름이 끼어 있다.

팽수는 구름을 무서워 하기에 구름이 없는 공간에서 비행 연습을 하고 싶어한다.

팽수는 초기에 z_s=1인 (x_s, y_s, z_s)에 있으며 (x_e, y_e, z_e) 위치에 도달하고자 한다.

팽수는 현재 어느 한 축과 완벽히 평행한 방향으로 비행하는 기술을 가지고 있으며 한 번의 날개짓으로 최대 하나의 단위 큐브를 이동할 수 있다.

목적지에 도달하기 위해 필요한 날개짓 수를 구하라.


입력

첫 줄에 VR 세계의 크기인 정수 n(1 \le n \le 100) 이 주어진다.

두 번째 줄에 팽수의 시작 위치 x_s,y_s,z_s가 주어진다. (1 \le x_s,y_s \le n, z_s=1)

세 번째 줄에 팽수의 목적 위치 x_e,y_e,z_e가 주어진다. (1 \le x_e,y_e,z_e \le n)

이어서 n개의 n \times n 2차원 공간이 주어진다.

i번째 2차원 공간의 좌상단 좌표는 (1,1,i)를 나타내며 높이 i를 의미한다.

2차원 공간의 행과 열은 각각 x,y에 해당한다.

'0'은 구름이 없는 단위 큐브, '1'은 구름이 있는 단위 큐브를 의미한다.

팽수의 시작 위치와 목적 위치에는 구름이 없다.


출력

팽수가 목적 위치에 도달하기 위해 해야 할 최소 날개짓의 수를 출력한다. 만약 도달할 수 없다면 '-1'을 출력한다.


부분문제

번호 점수 조건
#110점

n=2

#223점

구름이 없다.

#331점

z좌표가 1보다 큰 모든 위치에는 구름이 있다.

#436점

추가 제약 조건 없음.


예제1

입력
2
111
112
00
10
01
00
출력
1

팽수는 z축 방향으로 한번의 날개짓으로 목표 위치에 도달할 수 있다.


예제2

입력
3
231
111
000
010
000
111
111
111
111
111
111
출력
3

예제3

입력
3
211
322
000
010
110
010
001
001
101
110
000
출력
3

팽수는 (2,1,2) 위치로 이동한 다음 (2,2,2)로 이동하고 마지막으로 (3,2,2)로 이동하여 세 번의 날개짓으로 도달할 수 있다.


출처

COCI 2023/2024 Contest #2 2번

역링크