Camins hamiltonians palindròmics P31373


Statement
 

pdf   zip

thehtml

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 ‍
Public test cases

  • Input

    4
-pab
c-od
gf-p
ehi-

3
-aa
a-a
aa-

6
-yzyxx
z-yxyy
zz-xyz
yxy-xx
xyxy-y
zzyyx-

    Output

    2
6
70
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++