미로 9

남부 온타리오의 많은 옥수수 농가는 아래 그림처럼 옥수숫대 미로를 만든다. 미로는 곡식을 거둬들인 뒤인 가을에 만든다. 2010년을 위해 역대 최고의 미로를 설계할 시간이 아직 남아 있다.

밭은 옥수숫대로 덮여 있고, 나무나 건물처럼 옥수수가 자랄 수 없는 장애물 자리만 비어 있다. 키가 매우 큰 옥수숫대가 미로의 벽이 된다. 통로는 1m 정사각형 칸의 옥수숫대를 밟아 쓰러뜨려 만든다. 가장자리의 칸 하나가 입구이고, 칸 하나가 미로의 중심인 코어이다.

Jack은 해마다 옥수수 미로를 찾아가서 입구에서 코어까지 빠르게 길을 찾는 데 익숙하다. 여러분의 일은 어떤 옥수숫대를 밟을지 정해서, Jack이 지나야 하는 칸 수가 최대가 되도록 새 미로를 설계하는 것이다.

그림에서 #은 옥수숫대가 서 있는 칸이고, X는 나무처럼 밟을 수 없는 장애물 칸이다.

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

옥수수가 있는 칸을 밟으면 그 칸이 통로가 된다. 밟은 칸 하나는 입구로, 반드시 밭의 가장자리에 있어야 한다. 나머지 밟은 칸은 모두 안쪽에 있어야 한다. 목표는 입구에서 코어까지 최단 경로의 길이를 최대로 늘리는 것이다. 경로의 길이는 입구와 코어를 포함해 지나가는 밟은 칸의 수로 잰다. 두 칸은 둘 다 밟혀 있고 변을 공유할 때만 오갈 수 있다.

제출물에서 밟은 칸은 마침표(.)로 표시한다. 가장자리에 밟은 칸이 정확히 하나 있어야 한다. 예는 다음과 같다.

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

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

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

채점기가 입구(가장자리에 있는 유일한 칸)와 코어(Jack이 가장 멀리 걸어가야 하는 칸)를 정한다.

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

field9.txt는 크기 11x21의 밭을 나타낸다. 이 밭에 대해 입구에서 코어까지 최단 경로의 길이가 P인 미로를 만들어 maze9.txt로 저장한다. 이 하위 과제의 점수는 11과 $\min(11,\ 10P/10^4)$ 중 작은 값이다.