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 for you 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, which are extremely tall, form the walls of the maze. Pathways are created on a square grid by crushing m 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. You are designing a new maze, and your job is to determine which stalks to crush, so as to maximize the number of squares Jack must visit.
The grader will determine which square is the entrance (the only one on the perimeter) and which square is the core (the one that Jack must walk farthest to reach).
A map of the rectangular field is represented as text; for example, a m by m field with eight trees might be represented as:
##X#######
###X######
####X##X##
##########
##XXXX####
##########
The symbol #
represents a square with standing cornstalks, and X
represents a square with an obstacle (such as a tree) that cannot be crushed to form a pathway.
The field is transformed into a maze by crushing squares occupied by corn. One crushed square (the entrance) must be on the edge of the field. The 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 that Jack must pass through, including the entrance and the core. It is possible to pass from one square to another only if both are crushed and they share an edge.
In your submission, the crushed squares should be identified by periods (.
). Exactly one of the crushed squares should be on the perimeter. For example:
#.X#######
#.#X#...##
#...X#.X.#
#.#......#
#.XXXX##.#
##########
Below, for illustration purposes only, we mark the entrance E
, the core C
and remainder of the path using +
. The path length is .
#EX#######
#+#X#C+.##
#+++X#+X.#
#.#++++..#
#.XXXX##.#
##########
The folder maze.zip
contains several text files named field1.txt
field2.txt
etc. containing maps of cornfields. You are to copy them to files named maze1.txt
maze2.txt
etc., and transform them into valid mazes by replacing some of the #
symbols by periods.
Note: the Grading Server Public Test will award point per subtask for any valid solution (regardless of the path length). The Grading Server Release Test will award the remaining points. The total score for the task will be rounded to the nearest integer between and .
Subtask 1 [up to 11 points]
The field described above (of size ) may be found in the file field1.txt
. Create a maze for this field named maze1.txt
that has a shortest path from the entrance to the core with length . Your score for this subtask will be the minimum of and . Note that the sample solution scores points.
Subtask 2 [up to 11 points]
The file field2.txt
represents a field of size . Create a maze for this field named maze2.txt
that has a shortest path from the entrance to the core of length . Your score for this subtask will be the minimum of and .
Subtask 3 [up to 11 points]
The file field3.txt
represents a field of size . Create a maze for this field named maze3.txt
that has a shortest path from the entrance to the core of length . Your score for this subtask will be the minimum of and .
Subtask 4 [up to 11 points]
The file field4.txt
represents a field of size . Create a maze for this field named maze4.txt
that has a shortest path from the entrance to the core of length . Your score for this subtask will be the minimum of and .
Subtask 5 [up to 11 points]
The file field5.txt
represents a field of size . Create a maze for this field named maze5.txt
that has a shortest path from the entrance to the core of length . Your score for this subtask will be the minimum of and .
Subtask 6 [up to 11 points]
The file field6.txt
represents a field of size . Create a maze for this field named maze6.txt
that has a shortest path from the entrance to the core of length . Your score for this subtask will be the minimum of and .
Subtask 7 [up to 11 points]
The file field7.txt
represents a field of size . Create a maze for this field named maze7.txt
that has a shortest path from the entrance to the core of length . Your score for this subtask will be the minimum of and .
Subtask 8 [up to 11 points]
The file field8.txt
represents a field of size . Create a maze for this field named maze8.txt
that has a shortest path from the entrance to the core of length . Your score for this subtask will be the minimum of and .
Subtask 9 [up to 11 points]
The file field9.txt
represents a field of size . Create a maze for this field named maze9.txt
that has a shortest path from the entrance to the core of length . Your score for this subtask will be the minimum of and .
Subtask 10 [up to 11 points]
The file fieldA.txt
represents a field of size . Create a maze for this field named mazeA.txt
that has a shortest path from the entrance to the core of length . Your score for this subtask will be the minimum of and .
Implementation Details
- This is an output-only task.
- Implementation folder:
/home/ioi2010-contestant/maze/
(prototype: maze.zip) - To be submitted by contestant:
maze1.txt
maze2.txt
maze3.txt
maze4.txt
maze5.txt
maze6.txt
maze7.txt
maze8.txt
maze9.txt
mazeA.txt
. - Contestant interface: none
- Grader interface: none
- Sample grader:
grader.c
orgrader.cpp
orgrader.pas
- Sample grader input:
grader.in.1
grader.in.2
etc.
Note: the implementation folder contains very simple solutionsmaze1.txt
,maze2.txt
etc. Copy these tograder.in.1
grader.in.2
etc. for testing. - Expected output for sample grader input: if the input is a valid maze for subtask , the sample grader will output
OK N P
where is the path length.
Note: since DMOJ does not support uploading multiple files, you will instead submit a single file, which should adhere to the input and output specifications below.
Input Specification
The first line contains an integer , denoting the number of the test case.
The next line contains two integers , representing the height and width of the input corn field, respectively.
The next lines each contain characters, describing the input corn field.
The last lines are identical to the ones from the corresponding test case in the archive, and are provided for convinience only. Submissions can have up to characters, so it is possible to solve all test cases locally and encode the output mazes as part of your solution. For example, if you use two bits to represent each cell in an output maze, then storing all 10 outputs requires bits or bytes, which easily fits in less than characters.
Output Specification
Output lines each containing integers, describing the output maze.
Sample Input 1
1
6 10
##X#######
###X######
####X##X##
##########
##XXXX####
##########
Sample Output 1
#.X#######
#.#X#...##
#...X#.X.#
#.#......#
#.XXXX##.#
##########
Comments