Farmer John's farm is an N x N grid of fields (2 <= N <= 18), each labeled with a letter A..Z.

Each day, Bessie walks from the upper-left field to the lower-right field, each step taking her either one field to the right or one field downward. She keeps track of the string she generates from the letters she walks across, and gets disoriented if this string is a palindrome.

Please help Bessie determine the number of different palindromes she can form. Different ways of forming the same palindrome only count once.

Line 1: N. The remaining N lines contain the N rows of the grid; each row contains N characters in the range A..Z.

The number of distinct palindromes Bessie can form.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > US Open > Bronze