Evitant els tres en ratlla P51064

Donat un tauler n × m amb algunes caselles ja marcades, cal omplir-lo amb ‘O’ i ‘X’ de totes les maneres possibles evitant que hi hagi cap tres en ratlla horitzontal o vertical. Els tres en ratlla en diagonal sí que estan permesos.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguits de n files amb m caràcters. Si la casella ja està marcada, hi ha una ‘O’ o una ‘X’. Altrament, hi ha un punt. Podeu suposar que n · m està entre 1 i 20, i que inicialment no hi ha cap tres en ratlla.

Sortida

Per a cada cas, escriviu en ordre lexicogràfic (de dalt a baix, i dintre de cada fila d’esquerra a dreta) totes les maneres d’omplir el tauler sense que hi hagi cap tres en ratlla prohibit. Escriviu una línia amb 10 ‍guions al final de cada tauler, i una línia amb 20 asteriscs al final de cada cas.