問題
탐험가 동현이는 남미의 피라미드를 탐험중이다. 피라미드의 북쪽 부분에는 매우 크고 복잡한 미로가 있다. 미로는 정방형 블록으로 나뉘어 있으며 각 블록에는 바위가 있거나 비어있다.
바위가 없이 비어있는 블록의 바닥 중앙에는 갈고리가 있었다. 이 갈고리들을 유심히 관찰하던 동현이는 어느 두 곳의 갈고리와 그 사이의 갈고리들을 모두 밧줄에 연결한 후 밧줄을 팽팽하게 하면 비밀의 문이 열린다는 사실을 알아냈다. 그런데 문제는 밧줄의 양쪽 끝에 연결되는 갈고리가 어느 것인지 모른다는 것이다. 따라서 필요한 밧줄의 길이도 알 수가 없었다.
여러분에게 주어진 임무는 두 갈고리를 연결 할 때 필요한 밧줄의 최대길이를 알아내는 것이다.
輸入
첫 행에는 미로의 열의 크기 C와 행의 크기 R이 공백으로 구분되어 주어진다. (3 <= C, R <= 1000)
다음 행부터 R행에 걸쳐 미로의 정보가 입력된다. 바위가 있는 곳은 ‘#’, 비어 있는 곳은 ‘.’으로 표시되어 있다.
동현이는 상하좌우 ‘.’로 표시된 빈 블록으로만 이동한다.
미로는 임의의 두 빈 블록 사이의 경로는 유일하도록 만들어져 있다.
輸出
임의의 두 빈 블록이 있는 갈고리들을 연결할 때 필요한 밧줄 길이의 최대값을 출력한다.
範例 #1
3 3
###
#.#
###
0
範例 #2
7 6
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######
8
來源
Central Europe 1999, poj 1383
需要登入才能撰寫程式碼。