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 |
8 0 0 12 9 |
Решението
съответва
на
показаното
на горната
рисунка. |
Време
за работа на
програмата: 0.4 секунди за
тест
prof.
Carmen Popescu
"Gheorghe Lazar" Sibiu National High School
Contact: popescu.carmen@yahoo.com
Превод на
български:
Емил
Келеведжиев