Problem
La ferme de John est représentée par une grille de N×N champs (2≤N≤18), chacun étiqueté avec une lettre de l'alphabet. Par exemple,
ABCD
BXZX
CDXB
WCBA
Chaque jour, Besi la vache va du coin supérieur gauche au coin inférieur droit, se déplaçant soit d'une cellule vers la droite, soit d'une cellule vers le bas. Besi écrit la chaîne qui résulte de son itinéraire, construit à partir des lettres qu'elle a parcourues. Elle sera très contrariée si la chaîne résultante s'avère être un palindrome (elle se lit de la même manière du début à la fin et de la fin au début), car elle sera confuse dans quelle direction elle est allée.
Veuillez aider Besie à déterminer combien de palindromes différents elle peut former au cours de son voyage. Les différentes manières de former le même palindrome ne doivent être comptées qu'une seule fois. Par exemple, dans l'exemple ci-dessus, il existe plusieurs façons de former le palindrome ABXZXBA, mais il n'y a que 4 palindromes différents que Besi peut former ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.
FORMAT D'ENTREE :
La première ligne d'entrée contient N et les lignes N suivantes contiennent N < /strong> description du champ. Chaque ligne contient N caractères dans la plage A..Z.
FORMAT DE SORTIE :
Afficher le nombre de palindromes distincts que Besi peut former.
;
| Entrée |
Sortie |
4
ABCD
BXZX
CDXB
WCBA
4 |