Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2016
Fence
fence.c, fence.cpp, fence.c11, Fence.java, fence.py
Joe and Marty invented a new game. The game is called Save the sheep and it is played on a
rectangular grid. First, Joe draws a rectangle along the grid lines and then he fills some squares,
not all squares, inside the rectangle with light gray color, those squares represent the sheep.
Next, Marty fills one of the remaining squares inside the rectangle with black color, that square
represents the wolf. Then they both separately strive to fulfill the objective of the game which
is to draw the shortest possible fence around the sheep so that the wolf cannot reach them.
Specifically, the fence has to be drawn along the grid lines and it has to divide the grid into two
areas. All sheep should be in the area enclosed by the fence while the wolf should remain in the
area outside the fence. The fence must fit into the chosen rectangle, it may partially run along
the border of the rectangle. It must be a so called simple polygon, that is a polygon in which
no two non-adjacent edges touch or intersect each other.
The player who draws the shortest fence wins. Sometimes, it is not possible to draw the desired
fence and in such a case both players lose the game. Your task is to write a program that wins
the game whenever it is possible.
Input Specification
There are more test cases. Each case starts with a line containing two integers M , N (1 ≤
M, N ≤ 1000) separated by space which represent the height and the width of the rectangle.
Next, there are M lines representing the contents of the rectangle. Each line specifies one row
of the rectangle and it contains a string of length N . Each character in the string represents one
grid square and it is either capital letter "X", capital letter "O" or symbol "." (dot). Letter "X"
represents the wolf, letter "O" represents the sheep and the dot "." represents an unoccupied
square of the grid. Each animal occupies exactly one square in the grid and there is exactly one
wolf and at least one sheep in the rectangle.
Output Specification
For each test case, print a single line with one integer denoting the length of the shortest fence
that separates the sheep from the wolf according to the rules of the game. We suppose that each
square side in the grid has unit length. If it is not possible to draw the fence print "-1".
Sample Input
55
.....
..OOO
..OXO
O...O
..OOO
35
..O..
.OXO.
..O..
23
.O.
OXO
13
OXO
Output for Sample Input
26
-1
12
-1
Erratum
Due to an incorrect assumption, the original problem statement (as used in the 2016 CTU Open
Contest) required the fence to form a simple polygon. With this requirement, the problem turned
out to be much harder than expected. The test data and both authors' solutions correspond to
a variant of the problem under the following conditions:
· The fence may go across the same point twice, thus not being a simple polygon.
· It is still forbidden to use the same grid line more than once.
· The wolf must not be trapped by the fence. In other words, grid squares outside the
rectangle must be accessible to the wolf without crossing the fence.
The authors apologize for this error and express their gratitude to all teams participating in the
2016 CTU Open Contest for being so clever that no one even attempted to submit the incorrect
solution (that would be accepted). This helped a lot to keep the results of the competition valid
and fair.
