직접 가시선

이동통신망을 구축하고 운영하는 일은 비용이 많이 들고 복잡하다. 기지국(BTS)을 세우고 가동한 뒤에도, 기술자는 망의 상태를 파악하고 개선안을 세우기 위해 여러 가지 측정을 수행해야 한다.

기술자는 전계 강도, 송신 출력, 신호 품질을 측정하는 특수 장비를 들고 다닌다. 이 장비는 커다란 배낭에 들어 있으며, 기술자는 그것을 메고 한 기지국에서 다른 기지국으로 걸어서 이동한다. 배낭에는 측정값을 몇 초 동안만 담아 둘 수 있는 작은 캐시밖에 없으므로, 측정값은 곧바로 적외선(IrDA) 연결을 통해 기지국으로 전송되어야 한다. 적외선 연결은 기술자와 기지국 사이에 직접 가시선이 확보되어 있을 때에만 동작한다.

이웃한 두 기지국 사이를 걸어서 이동하는 경로 중, 매 걸음이 끝날 때마다 두 기지국 가운데 적어도 하나가 보이도록 하는 경로를 찾아라.

첫 줄에는 테스트 케이스의 수를 나타내는 양의 정수 T가 하나 주어진다. 각 테스트 케이스는 하나의 마을을 나타낸다.

마을은 P × Q개의 정사각형 칸으로 이루어진 직사각형 격자이며, 각 칸의 한 변은 1미터이다. 각 칸 (i, j)에는 그 지점의 지형 높이를 미터 단위로 나타내는 음이 아닌 정수 Z(i, j)가 주어진다. 따라서 마을은 단위 정육면체들로 이루어지며, 각 정육면체는 꽉 찼거나 비어 있고 '절반만 찬' 정육면체는 없다. 높이가 h인 칸에서는 높이 0부터 h-1까지의 정육면체가 꽉 차 있고, 그 위의 정육면체는 모두 비어 있다.

각 테스트 케이스의 첫 줄에는 공백으로 구분된 두 정수 P와 Q가 주어진다 (1 ≤ P, Q ≤ 200). 이어서 P개의 줄에 각각 공백으로 구분된 Q개의 정수가 주어지며, 이는 높이 Z(i, j)이다 (1 ≤ i ≤ P, 1 ≤ j ≤ Q, 0 ≤ Z(i, j) ≤ 5000). 테스트 케이스의 마지막 줄에는 두 기지국의 위치를 나타내는 네 정수 R1, C1, R2, C2가 주어진다 (1 ≤ R1, R2 ≤ P, 1 ≤ C1, C2 ≤ Q). 첫 번째 좌표 R은 행, 두 번째 좌표 C는 열을 뜻한다.

기술자는 한 번에 한 걸음씩, 이웃한 두 칸 사이를 북·남·서·동 네 방향 중 하나로 이동한다. 대각선 이동은 허용되지 않는다. 칸 A에서 칸 B로의 걸음은 높이 차가 크지 않을 때에만 허용된다. 즉 한 걸음에 최대 1미터까지 올라가거나 최대 3미터까지 내려갈 수 있다.

매 걸음이 끝날 때마다 두 기지국 가운데 적어도 하나가 보여야 한다(걸음 도중에는 잠시 보이지 않아도 되며, 그동안의 값은 캐시가 처리한다). 기지국과 기술자는 각자의 칸 중앙에서 지표면으로부터 정확히 0.5미터 높이에 있는 점, 즉 그 지점의 지형 바로 위에 놓인 단위 정육면체의 중심으로 본다. 이 두 점을 잇는 직선이 어떤 꽉 찬 정육면체의 내부도 통과하지 않을 때 기술자에게서 그 기지국이 보인다고 한다. 직선이 꽉 찬 정육면체에 닿는 것은 괜찮다. 적외선 빔은 모서리로만 맞닿은 두 정육면체 사이를 지날 수 있는데, 이때 빔은 두 정육면체에 닿기만 할 뿐 어느 쪽의 내부로도 들어가지 않기 때문이다.

위의 모든 규칙을 만족하는 가장 짧은 경로를 찾아라. 모든 걸음은 이웃한 칸 사이에서 이루어지고, 어떤 걸음도 너무 많이 오르거나 내려가지 않으며, 매 걸음이 끝날 때마다 적어도 하나의 기지국이 보여야 한다.

각 테스트 케이스마다 한 줄을 출력한다. 유효한 경로가 존재하면 The shortest path is M steps long.을 출력하며, 여기서 M은 가능한 최소 걸음 수이다. 그런 경로가 없으면 Mission impossible!을 출력한다.