Problem
Johns Farm wird durch ein Gitter aus N×N Feldern (2≤N≤18) dargestellt, von denen jedes mit einem Buchstaben des Alphabets gekennzeichnet ist. Zum Beispiel
ABCD
BXZX
CDXB
WCBA
Jeden Tag geht die Kuh von Besi von der oberen linken Ecke in die untere rechte Ecke und bewegt sich entweder eine Zelle nach rechts oder eine Zelle nach unten. Besi schreibt eine Zeichenfolge auf, die als Ergebnis ihrer Route erhalten wird, die aus den Buchstaben besteht, die sie durchlaufen hat. Er wird sehr verärgert sein, wenn sich die konstruierte Zeichenfolge als Ergebnis als Palindrom erweist (wird von Anfang bis Ende und von Ende zu Anfang gleichermaßen gelesen), da sie sich in welche Richtung verheddert.
Bitte helfen Sie Besi, die Anzahl der verschiedenen Palindrome zu bestimmen, die sie während ihrer Reise bilden kann. Die verschiedenen Möglichkeiten, dasselbe Palindrom zu bilden, sollten nur einmal berücksichtigt werden. Zum Beispiel gibt es im obigen Beispiel mehrere Möglichkeiten, ein ABXZXBA-Palindrom zu bilden, es gibt jedoch nur 4 verschiedene Palindrome, die Besi ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA bilden kann.
EINGABEFORMAT :
Die erste Eingabezeile enthält N, und die nachfolgendenN Zeilen enthalten N eine Feldbeschreibung. Jede Zeile enthält N Zeichen im Bereich A..Z.
AUSGABEFORMAT :
Geben Sie die Anzahl der verschiedenen Palindrome aus, die Besi bilden kann.
| Eingabe |
Ausgabe |
|
4
ABCD
BXZX
CDXB
WCBA
|
4 |