迷宫(Maze)

题目描述

小爱送给了小艾一个迷宫，这个迷宫是一个 $8\times 8$ 的网格图，每个格子上都有一个小写的英文字母。我们定义一个在迷宫上合法的路径为恰好经过了 $n$ 个格子，任意一次移动只移向相邻八联通的格子，且不经过任何重复格子的路径。

为了考验小艾，小爱给出了一个长度为 $n$ 的字符串 $s$，询问网格中有多少条合法的路径，满足路径上的字符连接成的字符串为 $s$。

输入格式

第一行输入一个字符串 $s$，表示小爱给出的字符串。

接下来 8 行，表示一个 $8\times 8$ 的字符方阵，表示整个迷宫。

输出格式

输出一行一个整数，表示满足条件的合法路径数。

样例输入 #1

aa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa

样例输出 #1

420

数据范围

• 对于 $30\%$ 的数据：$1\le n\le 4$。
• 对于 $60\%$ 的数据：$1\le n\le 8$。
• 对于 $100\%$ 的数据：$1\le n\le 11$。

知识点与难度

本题涉及的知识点从属于 GESP 六级（深度优先搜索、状态压缩、剪枝），难度等级：⭐⭐⭐⭐。

测试点分布