AIOC Banner

Problem: Packing Pentominoes

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


Packing Pentominoes

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:

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.

Input

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.

Output

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.

Sample Input

5 3
231
224
545
313
415

Sample Output

AAA
BCA
BCA
BCC
BBC

Scoring

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-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019,  4:19am AEST