Palindromic Paths

Time limit1sMemory limit256 MB

Summary

Count distinct palindromic strings spelled by right-down paths from the top-left to the bottom-right of an N by N letter grid.

Level: Medium7 of 10
Topics: DFS, Hash map, String
Solved: No attempts yet

Problem

Farmer John's farm is an $N \times N$ grid of fields ( $2 \le N \le 18$ ), and every field carries one uppercase letter from A to Z.

Every day the cow Bessie walks from the field in the upper left corner to the field in the lower right corner. Each step moves her one field to the right or one field down. She reads the letters of the fields she visits, the first and the last one included, so one walk spells a string of length $2N-1$ .

Bessie gets disoriented when that string is a palindrome. A palindrome reads the same forward and backward, so she loses track of the direction she walked.

Count the palindromes Bessie can spell. Two walks that spell the same palindrome count once.

Take this grid.

ABCD
BXZX
CDXB
WCBA

Several walks spell ABXZXBA, and Bessie can spell exactly four palindromes: ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.

Input

The first line contains $N$ . Each of the next $N$ lines contains one row of the grid as $N$ characters in the range A to Z.

Output

Print the number of distinct palindromes Bessie can spell.

Examples5

Example 1
Input
```
4
ABCD
BXZX
CDXB
WCBA
```
Expected output
```
4
```
Example 2
Input
```
2
AB
CA
```
Expected output
```
2
```
Example 3
Input
```
2
AB
CD
```
Expected output
```
0
```
Example 4
Input
```
2
AA
AA
```
Expected output
```
1
```
Example 5
Input
```
3
ABA
BAB
ABA
```
Expected output
```
1
```