Tres-en-ratlla estès P76384

Considereu el joc del tres-en-ratlla estès a un tauler de mides $3 \times n$, amb $n \ge 3$. Per torns, el primer jugador posa una ‘X’, el segon jugador posa una ‘O’, etc., fins que algun dels jugadors aconsegueix posar tres (o més) de les seves fitxes juntes en una línia formant un tres-en-ratlla, o fins que no es poden fer més jugades. Els tres-en-ratlla es poden fer horitzontalment, verticalment o en les dues diagonals.

Donat un tauler en el qual s’han fet algunes jugades, podeu decidir quin serà el resultat si els dos jugadors juguen perfectament a partir d’ara?

Entrada

L’entrada consisteix en la descripció de diversos taulers, cadascun amb $n$, seguida de tres línies amb $n$ caràcters cadascuna. Els punts indiquen posicions encara lliures. Suposeu $3 \le n \le 4$, que encara ningú ha aconseguit cap tres-en-ratlla, i que el nombre de posicions amb ‘X’ és o bé igual al nombre de posicions amb ‘O’ (li toca jugar al primer jugador) o bé un més que el nombre de posicions amb ‘O’ (i li toca jugar al segon jugador).

Sortida

Per a cada cas, escriviu el resultat de la partida suposant les millors jugades. Escriviu ‘X’ si guanyarà el primer jugador, ‘O’ si guanyarà el segon, o ‘E’ si serà empat.

Observació

La solució esperada és una programació dinàmica amb “memoization”. Les mides són tan petites perquè el nombre de taulers possibles creix molt ràpidament.