메두사와 전사들

0에서 N−1의 범위로 이루어진 N×N 크기의 어느 마을에 메두사가 살고 있습니다. 이 마을에는 도로가 깔려 있으며, 도로는 0, 도로가 아닌 곳은 1로 주어집니다.

메두사는 집에서 공원까지 산책을 나가기로 했습니다. 메두사의 집은 좌표 (Sr,Sc)에 있고, 공원은 좌표 (Er,Ec)에 위치해 있습니다. 메두사는 오직 도로만을 따라 최단 경로로 공원까지 이동합니다. 이때 메두사의 집과 공원은 항상 도로위에 있으며, 집과 공원의 좌표는 다름을 가정해도 좋습니다.