Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

ˇ

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.