회문 경로
Problem
John의 농장은 각각 알파벳 문자로 레이블이 지정된 N×N 필드(2≤N≤18)의 그리드로 표시됩니다. 예를 들어,
ABCD
BXZX
CDXB
WCBA
매일 Besi 소는 왼쪽 위 모서리에서 오른쪽 아래로 이동하며 오른쪽으로 한 칸 이동하거나 아래로 한 칸 이동합니다. Besi는 그녀가 걸은 글자로 만들어진 그녀의 경로에서 나온 문자열을 적습니다. 결과 문자열이 회문(처음부터 끝까지, 끝에서 처음까지 동일하게 읽음)으로 판명되면 그녀는 자신이 어느 방향으로 갔는지 혼란스러워할 것이기 때문에 매우 속상할 것입니다.
Besie가 여행하는 동안 얼마나 많은 회문을 형성할 수 있는지 알아내도록 도와주세요. 동일한 회문을 형성하는 다른 방법은 한 번만 계산해야 합니다. 예를 들어 위의 예에서 회문 ABXZXBA를 형성하는 방법은 여러 가지가 있지만 Besi가 ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA를 형성할 수 있는 회문은 4가지뿐입니다.
입력 형식:
입력의 첫 번째 줄은 N을 포함하고 후속 N줄은 N을 포함합니다. 필드 설명. 각 줄에는 A..Z.
범위의
N 문자가 포함됩니다.
<사업부>
출력 형식:
베시가 형성할 수 있는 고유한 회문의 수를 인쇄하십시오.
<사업부>
<몸>
| 입력 |
출력 |
|
<사업부>4
ABCD
BXZX
CDXB
WCBA
|
4 |