Cover a board P16898


Statement
 

pdf   zip

thehtml

You have an n × m board. In how many mays can you cover it with 1 × 2 pieces?

Input

Input consists of n and m. Assume 2 ≤ nm ≤ 40, and that nm is even.

Output

Print in lexicographical order all the ways to cover the board. To distinguish the pieces, the two cells of the same piece must have the same digit, and two adjacent pieces must have different digits. Apart from that, digits should be as small as possible. (See the sample output 3.) Print a blank line after every solution.

Public test cases
  • Input

    1 2
    

    Output

    00
    
    
  • Input

    2 2
    

    Output

    00
    11
    
    01
    01
    
    
  • Input

    2 4
    

    Output

    0010
    2210
    
    0011
    1100
    
    0100
    0122
    
    0101
    0101
    
    0110
    0220
    
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++