Nonograms P16479


Statement
 

pdf   zip

html

Nonogram is a solitaire game played on a n × n grid, where each cell has to be painted either black or white. Every row (and column) has a list of integer numbers, which correspond to the lengths of the runs of black squares in that row (or column), in order.

For instance, this is an example of solved nonogram:



Please write a program to solve nonograms.

Input

Input consists of several cases. Every case begins with a line with n, followed by n lines with the numbers of the i-th row, followed by n lines with the numbers of the j-th column. Assume 1 ≤ n ≤ 15. Every given nonogram has exactly one solution.

Output

For every case, print its number, followed by the solution of the nonogram, followed by a blank line.

Public test cases
  • Input

    15
    2 3 2
    9 2
    10 3
    10 3
    2 1
    1 1
    3
    3 1
    3 3
    4 3
    5 3
    6 2 1
    7 3
    1 4 1 3
    1 4 3
    10 2
    5 5
    3 10
    3 6
    3 5
    4 5
    4 2
    4 3
    3 1
    3 1 2
    7
    4 3
    2 1 4
    4
    4
    
    2
    2
    
    1
    1
    
    4
    2 1
    2
    1
    1 1
    1 1
    2
    2
    1 1
    

    Output

    Case #1
    XX...XXX.....XX
    XXXXXXXXX....XX
    XXXXXXXXXX..XXX
    XXXXXXXXXX..XXX
    XX.......X.....
    X.X............
    XXX............
    XXX........X...
    XXX......XXX...
    XXXX......XXX..
    .XXXXX...XXX...
    ..XXXXXX.XX.X..
    ..XXXXXXX.XXX..
    X.XXXX.X..XXX..
    X.XXXX....XXX..
    
    Case #2
    XX
    ..
    
    Case #3
    XX.X
    .XX.
    ..X.
    X..X
    
    
  • Information
    Author
    Xavier Martínez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Novè Concurs de Programació de la UPC - Semifinal
    Date
    2011-06-29