Входной файл: TANGRAM.IN Выходной файл: TANGRAM.OUT Время на тест: 5 секунд Тесты к задаче:Скачать
Танграм является одной из самых древних головоломок в мире.
Она появилась несколько тысячелетий назад в Китае и до сих пор является
любимым развлечением в странах Востока.
Название "танграм" (в Китае ее называли "чи-чао-тю",
что означает "хитроумный узор из семи частей"), по-видимому, было
придумано в середине XIX века каким-то английским или американским
"игрушечных дел" мастером, чье имя, к сожалению, до нас не
дошло.
Фигуркам, которые можно составить из семи элементов танграма, посвящено
множество альбомов и книг.
Чтобы понять причину удивительного долголетия этой старинной китайской
игры, достаточно определенным образам разрезать квадрат из плотного картона и
испытать свое искусство в складывании и придумывании новых фигурок. Схема
разрезания показана на рисунке 1. В каждой фигуре должны быть использованы все
семь элементов танграма.
Вашему вниманию предлагается слегка упрощенный вариант танграма.
На клеточном поле задается фигура. Каждая клетка может быть либо пустой,
либо закрашенной одним из пяти способов.
На рисунке показано, как задается фигура:
После раскроя танграма (см. рисунок 1) получим семь фишек:
Требуется написать программу, которая считывает из файла фигуру и пытается
составить ее из семи данных фишек. Если составить фигуру возможно, то
необходимо вывести один из вариантов. В противном случае выдать сообщение
"NO".
Формат ввода:
Ввод осуществляется из файла TANGRAM.IN:
N M
A11 A12 ... A1M
A21 A22 ... A2M
... ... ...
AN1 AN2 ... ANM
где N, M - размер фигуры, Aij - число от 0 до 5, показывающее
каким образом заполнена клетка (i,j). 0<N, M<20.
Формат вывода:
Вывод осуществляется в файл TANGRAM.OUT. Если составить фигуру невозможно
то выходной файл должен содержать строку " NO". В противном случае
необходимо для каждой фишки (с a по g) вывести ее расположение в формате:
X Y Angle
где X и Y - координаты левого верхнего угла квадрата, покрываемого фишкой,
X - номер строки в матрице (1<=X<=N), Y - номер столбца в матрице
(1<=Y<=M). Angle - угол поворота фишки по часовой стрелке (0, 90, 180,
270).
Примечание:
Здесь под фишкой подразумевается квадрат размером 2x2. Поэтому поворот, например, фишки f на 90 градусов будет выглядеть так: