Глава 42. Полимино

Постановка задачи
Идеи реализации
Рекурсивный подход
Кодирование фигур
Отросток
Утрата односвязности
Равные фигуры
Вывод результатов
XML и его приложения
Построение фигуры по клеткам
Класс Polyomino
Разработка
Класс Polyomino
Основная часть программы
Готовая программа

Автор выражает признательность Кириллу Гугаеву, ученику 11 класса (в 2009/2010 учебном году) за помощь в работе над этой главой.

На клетчатой бумаге закрашены n клеток так, что получившаяся фигура обладает следующими свойствами:

Связность

Каждая клетка фигуры соседствует хотя бы с одной другой клеткой (соседствует — значит имеет с соседней клеткой общую сторону; одной лишь общей вершины недостаточно для соседства):

соседние клетки (есть общая сторона)не соседние клетки (только общая вершина)

Односвязность

Не допускаются пустые области, ограниченные со всех сторон закрашенными клетками:

Фигуры с перечисленными свойствами называются полимино. Если n = 1 , фигуры называют мономино, при n = 2  — домино, при n = 3  — тримино, при n = 4  — тетрамино (это в точности фигуры тетриса), при n = 5  — пентамино, при n = 6  — гексамино, и т. д. В случае n-клеточной фигуры мы будем говорить о n-полимино.

Некоторые из n-полимино получаются друг из друга поворотами на углы, кратные 90°; такие фигуры считаются равными:

=

Если среди найденных n-полимино окажутся равные, из них выбирается только какая-нибудь одна.

Требуется написать программу polyomino.pl, которая для числа n, указанного в командной строке, отыщет все n-полимино. Форму выдачи результатов мы обсудим ниже.

Информатика-54© А. Н. Швец