Palindromic Paths (Bronze)

题目描述

农夫约翰的农场呈一个 $N \times N$ 的方格田地（$2 \le N \le 18$），每个格子都标有一个字母。例如：\nABCD\nBXZX\nCDXB\nWCBA\n\n每天，奶牛贝茜从左上角的格子走到右下角的格子，每一步要么向右走一格，要么向下走一格。贝茜会记录她在行走过程中经过的字母所生成的字符串。若这个字符串是一个回文串（正读与反读相同），她就会非常迷惑，因为她会搞不清自己是朝哪个方向走的。\n\n请帮助贝茜确定：在她的行走过程中，她能够形成多少种不同的回文串。形成同一个回文串的不同走法只计一次；例如，上面有多条路径会得到回文串 ABXZXBA，但贝茜一共只能形成四种不同的回文串：ABCDCBA、ABCWCBA、ABXZXBA、ABXDXBA。

输入格式

第一行输入为 $N$，接下来的 $N$ 行包含网格的 $N$ 行。每行包含 $N$ 个字符，字符范围为 A..Z。

输出格式

请输出贝茜能够形成的不同回文串的数量。

4\nABCD\nBXZX\nCDXB\nWCBA

4

提示

[题目来源：Brian Dean，2015]

标签: USACO|2015|Bronze

来源

USACO|2015|Bronze