미로 3

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

밭에는 옥수수가 자랄 수 없는 장애물(나무, 건물 등)이 몇 군데 있고, 나머지 부분은 옥수숫대로 덮여 있다. 옥수숫대는 매우 높아서 미로의 벽을 이룬다. 길은 1m 크기의 정사각형 칸에 있는 옥수숫대를 밟아 눕혀서 정사각형 격자 위에 만든다. 가장자리에 있는 격자 칸 하나가 입구이고, 격자 칸 하나가 미로의 중심이다.

잭은 해마다 옥수수 미로를 찾아가서 입구에서 중심까지 빠르게 길을 찾는 데 익숙하다. 여러분은 새 미로를 설계한다. 여러분이 할 일은 잭이 지나야 하는 칸의 수를 최대로 늘리도록 밟아 눕힐 옥수숫대를 정하는 것이다.

채점 프로그램이 입구(가장자리에 있는 유일한 칸)와 중심(잭이 가장 멀리 걸어가야 하는 칸)을 정한다.

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

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

#은 옥수숫대가 서 있는 칸을, X는 길을 만들려고 밟아 눕힐 수 없는 장애물(나무 등)이 있는 칸을 나타낸다.

옥수수가 있는 칸을 밟아 눕히면 밭이 미로가 된다. 밟은 칸 중 하나(입구)는 밭의 가장자리에 있어야 한다. 나머지 밟은 칸은 모두 안쪽에 있어야 한다. 목표는 입구에서 중심까지 가는 최단 경로를 최대로 만드는 것이다. 경로의 길이는 잭이 지나야 하는 밟은 칸의 수로 재며, 입구와 중심도 포함한다. 두 칸은 둘 다 밟혀 있고 변을 공유할 때에만 오갈 수 있다.

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

#.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 등의 이름으로 복사하고, # 기호 일부를 마침표로 바꿔 올바른 미로로 만든다.

field3.txt는 100x100 크기의 밭을 나타낸다. 이 밭으로 입구에서 중심까지 최단 경로 길이가 P인 미로를 만들어 maze3.txt라는 이름으로 저장한다. 이 부분 점수는 11과 10P/4000 중 작은 값이다.