미로 2

미국 온타리오 남부에서는 많은 옥수수 농가가 그림과 같은 옥수수대 미로를 만든다. 미로는 곡식을 수확한 뒤인 가을에 만들어진다. 2010년에 역대 최고의 미로를 설계하는 일을 도울 시간이 아직 남아 있다.

밭은 옥수수가 자랄 수 없는 장애물(나무, 건물 등)을 몇 개 제외하고 옥수수대로 덮여 있다. 키가 매우 큰 옥수수대가 미로의 벽을 이룬다. 길은 정사각형 격자 위에서 한 변이 1m인 정사각형 영역의 옥수수대를 짓밟아 만든다. 가장자리에 있는 격자 칸 하나가 입구이고, 격자 칸 하나는 미로의 중심이다.

잭은 매년 옥수수 미로를 찾아가며, 입구에서 중심까지 빠르게 길을 찾는 데 능숙하다. 여러분은 새 미로를 설계하고 있으며, 잭이 방문해야 하는 칸의 수를 최대로 만들도록 어떤 옥수수대를 짓밟을지 정하는 것이 임무이다.

채점기는 입구(외곽에 있는 유일한 칸)와 중심(잭이 가장 멀리 걸어가야 도달하는 칸)을 정한다.

직사각형 밭의 지도는 텍스트로 표현된다. 예를 들어 6m × 10m 밭에 나무 8그루가 있으면 다음과 같이 나타낸다.

##X#######
###X######
####X##X##
##########
##XXXX####
##########

#은 옥수수대가 서 있는 칸을, X는 나무처럼 짓밟아 통로로 만들 수 없는 장애물 칸을 나타낸다.

밭은 옥수수가 있는 칸을 짓밟아 미로가 된다. 짓밟은 칸 하나는 반드시 밭의 가장자리에 있어야 하며, 이것이 입구가 된다. 나머지 짓밟은 칸은 모두 내부에 있어야 한다. 목표는 입구에서 중심까지 가는 최단 경로의 길이를 최대로 만드는 것이다. 이 길이는 입구와 중심을 포함하여 잭이 지나는 짓밟은 칸의 수로 잰다. 두 칸은 둘 다 짓밟은 칸이고 변을 공유할 때에만 오갈 수 있다.

아래 그림에서 입구는 E, 중심은 C로 표시하고, 나머지 경로는 +로 표시했다. 경로의 길이는 12이다.

#EX#######
#+#X#C+.##
#+++X#+X.#
#.#++++..#
#.XXXX##.#
##########

제출물에서는 짓밟은 칸을 마침표(.)로 표시한다. 짓밟은 칸 중 정확히 하나는 외곽에 있어야 한다. 예를 들면 다음과 같다.

#.X#######
#.#X#...##
#...X#.X.#
#.#......#
#.XXXX##.#
##########

/home/ioi2010-contestant/maze 폴더에는 field1.txt, field2.txt 등의 이름을 가진 텍스트 파일이 여러 개 들어 있다. 이 파일들을 maze1.txt, maze2.txt 등의 이름으로 복사한 뒤, #의 일부를 마침표로 바꿔 유효한 미로로 만든다.

field2.txt는 100x100 크기의 밭을 나타낸다. 이 밭에 대해 입구에서 중심까지 최단 경로의 길이가 P인 미로를 만들고, 이름을 maze2.txt로 저장한다. 이 부분 문제의 점수는 11과 $10P/4000$ 중 작은 값이다.