pento

Пентомино наричаме всяко подреждане на 5 еднакви квадратчета, при което всяко от квадратчетата има обща страна с поне едно друго квадратче. Съществуват 12 различни начина за такова подреждане, дадени по-долу с техните номера:

Отделните пентомино могат да се поставят едно до друго, като по тази начин се образуват различни форми. При това те могат да се завъртат на  90,  на 180 или на 270 градуса, или да взема огледалното им изображение. Пример за една такава форма, наподобяваща буквата H и използваща всичките 12 пентомино е дадена по-долу:

Задача

При дадена форма, намерете метод за получаването й с използването на всичките 12 различни пентомино, като се взема точно по веднъж всяко от 12-те пентомино. Формата е зададена като матрица от m реда и n стълба с елементи 0 и 1. Елементът 1 задава квадратче, което трябва да се покрие, а елементът 0 – квадратче, което трябва да остатне празно. Не трябва да има припокриване на отделните пентомино. В решението на задачата трябва единиците в първоначалната матрица да бъдат заменени от съответните номера на използваните пентомино.

Вход

Първият ред на входния файл pento.in съдържа числата m и n, разделени с интервал. Всеки от следващите m реда съдържа n двоични цифри, определящи формата, която трябва да се покрие с 12-те различни пентомино.

Изход

Файлът pento.out трябва да съдържа m реда, всеки съдържащ n цели неотрицателни числа от 0 до 12, показвaщи начина на покриване.

Ограничения

Пример

pento.in

pento.out

Задележка

12 6
110011
110011
110011
111111
111111
111111
111111
111111
110011
111011
111011
111001

8 0 0 12 9
8 8 0 0 12 9
2 8 0 0 12 9
2 2 2 12 12 9
2 7 6 6 10 9
7 7 7 6 10 10
7 3 3 6 6 10
3 3 1 1 1 10
3 4 0 0 1 11
4 4 4 0 1 11
5 4 5 0 11 11
5 5 5 0 0 11

Решението съответва на показаното на горната рисунка.

Време за работа на програмата: 0.4 секунди за тест

 

prof. Carmen Popescu
"Gheorghe Lazar" Sibiu National High School
Contact: popescu.carmen@yahoo.com

Превод на български: Емил Келеведжиев