Want to try solving this problem? You can submit your code online if you log in or register.

**Input File:** `pentin.txt`

**Output File:** `pentout.txt`

**Time Limit:** 0.2 second

Times have been bad for gaming companies, and the manufacturers of dominoes and pentominoes have been forced to merge. To mark this event and perhaps even make some income, they have released a curious new puzzle as follows.

You are given a rectangular board divided into squares as illustrated below. Every square of this board has been marked with one of the digits 1, 2, 3, 4 or 5. Your task is to cover this board with pentominoes.

A *pentomino* is a plastic tile consisting of five squares connected
along their edges. Some sample pentominoes are illustrated below.

Note that the squares forming a pentomino must be connected along their
edges; diagonal connections are not sufficient. Thus for instance the
following is *not* a valid pentomino.

Note that any tile consisting of five connected squares is a valid pentomino; the examples above only represent a small selection of the available shapes.

But a puzzle is not a puzzle without a catch. Your restrictions are that you must:

- cover the entire board with pentominoes so that no pentominoes overlap;
- place the pieces so that each pentomino covers each of the digits 1, 2, 3, 4 and 5 precisely once.

A valid solution for the board above is illustrated below.

Since this is an informatics competition, you are asked to replace hours of pleasure with a computer program that will solve the puzzle for you while you sit down and watch TV.

The input file will consist of a description of a single board.
The first line of input will be of the form *r* *c*,
where *r* is the
number of rows and *c* is the number of columns in the board. You are
guaranteed that the board will contain at least 5 and at most 60 squares
in total.

Following this will be *r* lines, each containing *c* digits
representing the markings on a single row of the board.
There will be no spaces between these digits.

Your output must describe a single solution to the puzzle.

Pentominoes should be labelled using letters of the alphabet. It does not matter in which particular order they are labelled or which particular letters are used.

The output file must contain precisely *r* lines, each containing
*c* upper-case letters indicating which pentomino is covering
each square on that particular row of the board (thus each letter that
you use appears precisely five times in the output file). There should be no
spaces between these letters.

The rows and columns of the board in the output file must match the rows and columns of the board in the input file.

You may assume there is always a solution to the puzzle. If there is more than one solution then any solution will suffice.

5 3 231 224 545 313 415

AAA BCA BCA BCC BBC

The score for each input file will be 100% if a correct solution is written to the output file and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 21 September 2021, 10:17am AEST