Maze 9

In southern Ontario, many corn farmers create cornstalk mazes like the one shown. The mazes are created in the fall, after the grain has been harvested. There is still time to help design the best maze ever for 2010.

A field is covered with corn stalks except for a few obstacles (trees, buildings and the like) where corn cannot grow. The stalks are extremely tall and form the walls of the maze. Pathways are created on a square grid by crushing 1m square areas of stalks. One grid square on the edge is the entrance, and one grid square is the core of the maze.

Jack visits a corn maze every year and has become adept at finding his way quickly from the entrance to the core. Your job is to design a new maze by choosing which stalks to crush, so that the number of squares Jack must pass through is as large as possible.

In the map, # is a square with standing cornstalks, and X is an obstacle (such as a tree) that cannot be crushed.

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

The field becomes a maze by crushing squares that contain corn. One crushed square, the entrance, must be on the edge of the field. All other crushed squares must be in the interior. The objective is to maximize the shortest path from the entrance to the core, measured by the number of crushed squares on the path, including the entrance and the core. Two squares can be passed between only if both are crushed and they share an edge.

In your submission, mark the crushed squares with periods (.). Exactly one crushed square must be on the perimeter. For example:

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

Below, for illustration only, the entrance is marked E, the core C, and the rest of the path +. The path length is 12.

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

The grader determines which square is the entrance (the only one on the perimeter) and which square is the core (the one Jack must walk farthest to reach).

The folder /home/ioi2010-contestant/maze contains several text files named field1.txt, field2.txt, and so on, each holding a map of a cornfield. Copy them to files named maze1.txt, maze2.txt, and so on, and turn each into a valid maze by replacing some of the # symbols with periods.

The file field9.txt describes a field of size 11x21. Create a maze for this field named maze9.txt whose shortest path from the entrance to the core has length P. The score for this subtask is the minimum of 11 and $\min(11,\ 10P/10^4)$.