SLLSSSL
LLLSLLL
LSLSLSS
LSLSLLL
SLLSLSS

주몽이가 어떤 섬에 도착했다! 이 섬에는 어딘가에 음식이 숨겨져 있다고 한다. 하지만 불행하게도 주몽이와 음식의 거리는 가능한 최대값이다. 주몽이와 음식의 좌표를 구하자.

육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안된다.

예를 들어 위와 같이 지도가 주어졌다면 주몽이는 (0, 3)에 있게 되고, 음식은 (1, 4)에 있게 된다. 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

이 섬의 지도가 주어질 때, 주몽이와 음식 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하자.

\(1 ≤ n ≤ 100\), \(1 ≤ m ≤ 100\)

지도의 세로 길이 n, 가로 길이 m이 첫줄에 주어진다.
그리고 지도가 주어진다.

주몽이와 음식 사이의 거리를 출력한다.

joomongogo 작성

출처 정올 1462