Camins hamiltonians palindròmics P31373

Teniu un graf dirigit amb n vèrtexs. El graf és complet, és a dir, té tots els n(n−1) arcs. Cada arc està etiquetat amb una lletra minúscula. Donat un camí dins del graf, aquest genera la paraula formada per la concatenació de les lletres dels arcs visitats pel camí.

Un camí hamiltonià d’un graf és un camí que passa exactament una vegada per cada vèrtex. Un graf complet en té exactament n!. Quants d’aquests camins generen un palíndrom (un cap-i-cua)? Aquestes paraules lògicament tindran n−1 lletres.

Entrada

L’entrada consisteix en diversos grafs, cadascun amb el nombre de vèrtexs n, seguit d’n ‍línies amb n caràcters cadascuna. El caràcter a la fila x, columna y indica l’etiqueta de l’arc x → y. La diagonal només té guions. Podeu suposar 3 ≤ n ≤ 12.

Sortida

Per a cada graf, escriviu quants camins hamiltonians té que generin un palíndrom.

Puntuació

• Cas A:  ‍ Casos on n ≤ 6, com l’exemple d’entrada.  ‍25% Punts ‍

• Cas B:  ‍ Casos on n ≤ 9.  ‍30% Punts ‍

• Cas C:  ‍ Resta de casos.  ‍45% Punts ‍