<PREV Problem:
NEXT>
Solved by 39 users: Juk, NSI, DD, dan, Dmitry_Gozman, Anju7a, bloodmage, tomek, wojtekt, Huang_SR, JohnJones_001, Ravent, lcosvse, zmy, Smitty, g201513, marek.cygan, andyzh1314, vi002, zinccopper, mY_himEKiD, ajaysomani, WsemirZ, tourist, zloy_mipt, Moonlight, zhekas, UdH-WiNGeR, defrager, topspin, RAVEman, knightry, Dest, ripatti, fuckme, katuxa, checkil, NIGHTFIT, avg79.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Japanese Crossword

Time limit = 5 second(s)

This is an interesting problem for Japanese crosswords solvers. You are given puzzle and should output the maximal number of possible solutions. All the crosswords in tests cases are not larger than 20 x 20. Answer does not exceed 30 000.

Input. The first line contains two numbers — M and N — number of rows and columns in the test. The following M + N lines contain information about sizes of black groups in each column (first M lines) and row (next N lines). Zero is used to terminate the group. If there are no black cells, then the line will contain only one zero.

Output. The maximal number of different solutions for the given puzzle.

Input#1
2 2
1 0
1 0
1 0
1 0
Output#1
2
Input#2
2 3
1 1 0
3 0
2 0
1 0
2 0
Output#2
1

Author:
Eugene Vishnyakov
April 26, 2005y.

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


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

SW soft NIX
ID = 23.20.166.68