문제

남부 오타리오 주에서 옥수수 밭을 경작하는 많은 농부는 아래와 같이 옥수수 미로를 만듭니다. 미로는 옥수수가 경작된 후인 가을에 만들어집니다. 아직 2010년 최고의 미로를 디자인할 시간이 남아있습니다.

옥수수 밭은 옥수수가 자랄 수 없는 (나무, 빌딩 등) 장애물이 있는 몇몇 구역을 제외하면 모두 옥수수 줄기로 덮여 있습니다. 엄청나게 긴 줄기는 미로의 벽이 됩니다. 통로는 줄기를 잘라 1m 정사각형 크기의 격자 형태로 만들어집니다. 가장자리의 격자 하나는 입구가 되며, 또 다른 격자 하나는 미로의 중심이 됩니다.

잭은 매년 옥수수 미로를 방문해 입구부터 중심까지 빠르게 통로를 찾는 것에 능숙합니다. 당신은 잭이 방문해야만 하는 정사각형의 수가 최대가 되도록 미로를 디자인하려면 어떤 줄기를 잘라야 하는지 계산해야 합니다. 

어떤 정사각형이 (둘레 중 딱 하나의) 입구가 되고 어떤 정사각형이 (잭이 도달하기 위해 가장 오래 걸어야 하는) 중심이 될 것인지는 채점 기계가 정합니다.

직사각형 밭의 지도는 텍스트로 주어집니다; 예를 들어, 나무가 8개인 6m * 10m 크기의 밭은 아래와 같이 주어집니다:

(그림 참고)

기호 #은 옥수수 줄기가 있는 정사각형을, X는 (나무 등의) 장애물이 있어 통로로 뚫을 수 없는 정사각형을 나타냅니다. 

밭은 옥수수가 있는 정사각형의 옥수수를 부숨으로써 미로가 됩니다. (입구를 만들기 위해) 부순 정사각형 중 하나는 무조건 옥수수 밭 가장자리에 있어야 합니다. 부순 정사각형 중 다른 하나는 무조건 안에 있어야 합니다. 당신의 목표는 입구와 중심을 포함해 잭이 지나치는 부서진 정사각형의 수로 계산되는 입구부터 중심까지 최소 거리를 최대치로 만드는 것입니다. 두 정사각형이 모두 부서진 상태고 한 변을 공유해야만 한 정사각형에서 다른 정사각형으로 넘어갈 수 있습니다.

답을 제출할 때, 부서진 정사각형은 온점(.)으로 표시합니다. 부서진 정사각형 중 정확히 하나만 밭의 둘레에 있어야 합니다. 아래는 예시입니다:

(그림 참고)

아래는 오로지 설명을 위해 입구를 E, 중심을 C, 나머지 경로를 +로 표시한 예시입니다. 경로의 길이는 12입니다.

 /home/ioi2010-contestant/maze에는 field1.txt, field2.txt 등 옥수수 밭의 지도를 담은 여러 텍스트 파일이 있습니다. 당신은 그 파일을 maze1.txt, maze2.txt 등의 파일에 복사해 기호 # 중 일부를 온점으로 바꿔 미로를 생성해야 합니다.

field1.txt에는 위에 묘사한 (6x10 크기의) 밭이 있습니다. 이 파일에 대해 입구부터 중심까지 최소 거리가 길이 P인 미로를 maze1.txt에 생성합니다. 이 서브태스크의 점수는 11과 10^P/20  중 최솟값입니다. 참고로 예시 해결책의 점수는 3.98점입니다.