In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
In a fantasy world, there is a large island of a rectangular shape. The sides of the island happen to be exactly miles and miles long, and the whole island is divided into a grid of areas. Some of the areas are uninhabited, and the rest are occupied by villages of fantasy beings: elves, humans, dwarves, and hobbits. Each area contains at most one village. Two villages are considered neighbours if their areas share a side.
Recently, the villages became terrified of the Great Evil. In order to feel safer, each village has decided to form military alliances with some of its neighbours. An alliance always involves two neighbouring villages, and it is a mutual and symmetric agreement.
Depending on the species living in the village, the inhabitants will not feel safe unless a specific configuration of alliances is formed:
In other words, except for humans each village requires a particular number of alliances, but does not care which neighbours will be its allies. For humans there is an additional restriction: the allied neighbours must not be on opposite sides of the village.
The conditions must be fulfilled irrespective of the position of the village on the map. For example, a dwarf village desires three alliances. If it is located on the coast, this means that it must have alliances with all three neighbours. If there is a dwarf village in a corner of the island, its inhabitants will never feel safe.
For a given island description, your task is to decide whether it is possible to form alliances so that all inhabitants of the island will feel safe. In case of a positive answer, your task is also to suggest one viable configuration of alliances. In case of multiple solutions, choose an arbitrary one.
The first line of the input contains two integers and specifying the size of the island. The following lines encode a description of the island. Each line consists of space-separated numbers between 0 and 4:
In all test cases assume that .
In test cases worth a total of 55 points we have . Out of these, in test cases worth 15 points .
Another batch of test cases worth 10 points contains maps with only uninhabited areas and human villages. (This batch is not included in the test cases worth 55 points.)
If there is no solution, output a single line with the string "Impossible!" (quotes for clarity). Otherwise, output one valid map of alliances in the following format.
Each area should appear in the output as a matrix of characters. If the area is uninhabited, the corresponding section of the output will be filled with '.' (dot) symbols. If the area has a village there should be a a symbol 'O' (uppercase letter O) in the middle representing the village itself, and there should be symbols 'X' (uppercase letter X) representing a configuration of its allies. The rest of the matrix should be filled with '.' (dot) symbols.
For each village type, all possible layouts of alliances are shown in the image below.
For the input data:
3 4 2 3 2 0 3 4 3 0 2 3 3 1
the correct result is:
............ .OXXOXXO.... .X..X..X.... .X..X..X.... .OXXOXXO.... .X..X..X.... .X..X..X.... .OXXOXXOXXO. ............
and for the input data:
1 2 2 1
the correct result is:
Task author: Marek Zeman.