보물섬
면접 대비시간 제한1초메모리 제한512 MB
육지와 물로 이루어진 격자에서 서로 도달 가능한 두 육지 칸 사이의 최단 이동 시간 중 최댓값을 구합니다.
문제
후크 선장은 직사각형 모양의 보물 지도를 발견했다. 지도는 여러 칸으로 나뉘어 있으며, 각 칸은 육지(L) 또는 바다(W)로 표시되어 있다. 육지 칸에서는 상하좌우로 이웃한 육지 칸으로만 이동할 수 있고, 한 칸 이동하는 데 1시간이 걸린다.
보물은 서로 이동할 수 있는 육지 칸 쌍 중 최단 이동 시간이 가장 길어지는 두 칸에 나뉘어 묻혀 있다. 가능한 두 육지 칸 사이의 최단 이동 시간 중 최댓값을 구하시오.
입력
첫째 줄에 보물 지도의 세로 크기 H와 가로 크기 W가 빈칸을 사이에 두고 주어진다. 다음 H개의 줄에는 L과 W로 이루어진 지도가 주어지며, 한 줄의 문자 사이에는 빈칸이 없다.
보물 지도의 세로와 가로의 크기는 각각 50 이하이다.
출력
보물이 묻혀 있는 두 육지 칸 사이를 최단 거리로 이동하는 데 걸리는 시간을 출력한다.