Avoiding three-in-a-row P51064


Statement
 

pdf   zip

thehtml

Given an n × m board with some cells already marked, fill it with ‘O’ and ‘X’ in all the possible ways, but avoiding any horizontal or vertical three-in-a-row. The diagonal three-in-a-row are allowed.

Input

Input consists of several cases. Every case begins with n and m, followed by n rows with m ‍characters each. If the cell is already marked, there is an ‘O’ or an ‘X’. Otherweise, we have a period. You can assume that n · m is between 1 and 20, and that there is no three-in-a-row initially.

Output

For every case, print in lexicographical order (from top to bottom, and inside each row, from left to right) all the ways to fill the board without any forbidden three-in-a-row. Print a line with 10 dashes at the end of each board, and a line with 20 asterisks at the end of each case.

Public test cases
  • Input

    2 2
    X.
    .X
    
    4 5
    .X...
    OXO.O
    ..O..
    ...X.
    
    3 4
    .X..
    ...O
    .XX.
    

    Output

    XO
    OX
    ----------
    XO
    XX
    ----------
    XX
    OX
    ----------
    XX
    XX
    ----------
    ********************
    ********************
    OXOX
    XOXO
    OXXO
    ----------
    XXOX
    OOXO
    OXXO
    ----------
    XXOX
    XOXO
    OXXO
    ----------
    ********************
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++