남부 온타리오의 많은 옥수수 농가는 아래 그림처럼 옥수수대 미로를 만든다. 미로는 곡식을 수확한 뒤인 가을에 만든다. 2010년에 세상에서 가장 좋은 미로를 설계할 시간이 아직 남아 있다.

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

Jack은 매년 옥수수 미로를 찾아가며 입구에서 중심까지 빠르게 길을 찾는 데 능숙해졌다. 당신은 새 미로를 설계하고 있다. 당신의 일은 Jack이 지나야 하는 칸의 수를 최대로 만들도록 어느 옥수수대를 짓밟을지 정하는 것이다.

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

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

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

기호는 옥수수대가 서 있는 칸이다. X 기호는 나무처럼 짓밟아 통로로 만들 수 없는 장애물이 있는 칸이다.

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

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

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

아래 그림은 설명을 위한 것이다. 입구는 E, 중심은 C, 나머지 경로는 +로 표시했다. 경로 길이는 12다.

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

폴더 /home/ioi2010-contestant/maze에는 field1.txt, field2.txt 등의 이름으로 옥수수밭 지도가 든 텍스트 파일이 여러 개 있다. 이 파일을 maze1.txt, maze2.txt 등의 이름으로 복사하고, # 일부를 마침표로 바꿔 올바른 미로로 만든다.

field6.txt는 11x11 크기의 밭을 나타낸다. 이 밭의 미로를 maze6.txt 파일로 만들어라. 입구에서 중심까지의 최단 경로 길이가 P여야 한다. 이 하위 과제의 점수는 11과 10P/54 중 작은 값이다.