<ПРЕД Задача:
СЛЕД>
Задачу решили 14 пользователей: defrager, UdH-WiNGeR, WsemirZ, dan, murphy, fetetriste, TTLovePP, Yagi_Arthur, RAVEman, Rizvanov, VladimirChelnokov, Dest, ripatti, topspin.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Пентамино

Time limit = 5 секунд

Полимино — связная фигура, составленная из одноклеточных квадратов, примыкающих друг к другу по строне. Другими словами — это связная клеточная фигура, которую можно обойти ладьёй. Пентамино — это полимино, состоящее из 5 клеток, как нетрудно убедиться, существует ровно 12 пентамино, с точностью до поворотов и осевых симметрий.

Задача состоит в том, можно ли клеточную фигуру из 60 клеток покрыть всем набором пентомино, то есть каждое пентомино должно использоваться ровно 1 раз, и каждая клетка этой 60 — клеточной фигуры должна быть покрыто каким-нибудь пентамино.

Вход. Вход состоит из чисел M и N, и прямоугольника размером M*N (M строк, N столбцов), состоящего из нулей и едениц из которых ровно 60 — единицы, остальные -нули.

Выход. Выход должен содержать слово YES, если клеточную фигуру из 60 единиц можно покрыть набором пентомино, и NO в противном случае.

Вход#1
10 6
111111
111111
111111
111111
111111
111111
111111
111111
111111
111111

Выход#1
YES

Вход#2
11 13
0000100000000
0011111000000
0000111010000
0000111010110
1111111111111
1111111111100
1111111100000
0001111000000
0000111000000
0000111000000
0000011000000

Выход#2
NO

Автор:
Вообще, первооткрывателем пентомино и задач с ним связанных является С.В.Голомб, так что здесь должно быть упомянуто и его имя.
27 марта 2009

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 18.210.24.208