<PREV Problem:
NEXT>
Solved by 14 users: defrager, UdH-WiNGeR, WsemirZ, dan, murphy, fetetriste, TTLovePP, Yagi_Arthur, RAVEman, Rizvanov, VladimirChelnokov, Dest, ripatti, topspin.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Pentamino

Time limit = 5 seconds

Polyomino is a connected figure made of one-cell squares, adjacent by its sides. By other words, it is consecutive one-cell figure that could be traced by chess rook. Pentamino is polyomino consisted of 5 one-cell elements. There are exactly 12 different pentaminoes (rotations and reflections do not create new ones).

The problem is to verify whether given 60 one-cells elements figure can be covered with full set of pentaminoes. That means each of 12 figures should beg used exactly once and each cell of the source figure should be covered.

Input. Input contains numbers M and N and rectangle M*N (M rows and N columns) with '0' and '1' elements. There are exactly 60 '1' cells in the rectangle.

Output. Output must contain a single word YES if the given 60-cells figure can be covered with full set of pentaminos and NO otherwise.

Input#1
10 6
111111
111111
111111
111111
111111
111111
111111
111111
111111
111111

Output#1
YES

Input#2
11 13
0000100000000
0011111000000
0000111010000
0000111010110
1111111111111
1111111111100
1111111100000
0001111000000
0000111000000
0000111000000
0000011000000

Output#2
NO

Author:
Here must be also name of Golomb, the inventor of pentamino.
27 Marth 2009

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 54.162.181.75