El joc de l'OSO P41805

L’Anna i en Bernat estan jugant al joc de l’OSO, en una versió simplificada. Suposeu un tauler n × m, inicialment buit, on per torns s’hi ha de posar una ‘S’ o una ‘O’ a qualsevol casella lliure. Sempre comença a jugar l’Anna. Guanya el primer que aconsegueix escriure “OSO” horitzontalment o verticalment (no diagonalment). Si el tauler s’omple sense que ningú aconsegueixi fer un “OSO”, la partida acaba en empat.

Donades les n · m jugades que s’intentaran fer en un tauler inicialment buit, escriviu el nom del guanyador o bé si hi ha hagut empat. A més, escriviu el contingut del tauler quan s’ha acabat la partida, ja sigui perquè algú ha guanyat o perque s’han omplert totes les posicions.

Entrada

L’entrada té diverses partides. Cada partida comença amb les mides del tauler n i m, seguides de n · m jugades, cadascuna amb una fila entre 0 i n−1, una columna entre 0 i m−1, i un caràcter que és ‘S’ o ‘O’. Suposeu 1 ≤ n · m ≤ 10⁵, i que totes les posicions donades són diferents.

Sortida

Per a cada partida, escriviu “Anna”, “Bernat”, o bé “empat”. A continuació, escriviu l’estat final de la partida. Marqueu amb punts les posicions on no s’ha arribat a jugar. Escriviu una línia buida al final de cada cas.