A - Yokohama Phenomena / 横滨现象

版权信息： ICPC International Collegiate Programming Contest Asia Regional Contest, Yokohama, 2023/11/26

任务总览

题目描述

你知道横滨现象吗？这种现象发生在三位程序员围坐在一张桌子旁，共同握住一支笔，并把笔悬在一个标有字母的方格板上。在这块方格板上，划有一个网格，每个小方格上都标有一个字母。虽然参与者并没有故意移动笔，但它的笔尖仿佛有了意志，自动落在标有字母 Y 的某个方格上，之后开始在网格上移动。笔尖经过的方格依次标有字母 ​O​, ​K​, ​O​, ​H​, ​A​, ​M​, ​A​，然后停在标有字母 A 的方格上。我们称这样的轨迹为 YOKOHAMA 路径。

YOKOHAMA 路径的定义如下：

• 它是一个由八个方格组成的序列，且这些方格按照给定的顺序排列。
• 每个方格（除了第一个）与它前一个方格是边相邻的。
• 这八个方格上的字母顺序为：​Y, O, K, O, H, A, M, A​。

需要注意的是，同一个方格可以在路径中出现多次。

你的任务是计算在给定的网格中，能找到多少条不同的 YOKOHAMA 路径。

输入格式

输入包含一个测试用例，格式如下：

n m
x11 
.
.
.
xn1 
xnm

• 第一行包含两个整数 n 和 ​m​，表示网格的行数和列数，满足 1 ≤ n ≤ 10 和 ​1 ≤ m ≤ 10​。
• 接下来的 n 行描述网格中的字母。每个字母为 A, H, K, M, O, Y 之一。

输出格式

输出一个整数，表示不同的 YOKOHAMA 路径的数量。

输入输出示例

输入示例 1

2 4
YOHA
OKAM

输出示例 1

8

输入示例 2

3 4
YOKH
OKHA
KHAM

输出示例 2

0

输入示例 3

3 6
MAYOHA
AHOKAM
MAYOHA

输出示例 3

80

题目分析

1. 任务目标：
   • 给定一个网格，其中每个方格上都有字母 ​A, H, K, M, O, Y​，我们需要计算不同的 YOKOHAMA 路径的数量。
   • 每个路径必须遵循固定的字母顺序，并且每个字母只能通过边相邻的方格连接。
2. 关键观察：
   • 为了找到 YOKOHAMA 路径，首先需要找到字母 Y 的位置，然后通过边相邻的方格依次访问字母 ​O​, ​K​, ​O​, ​H​, ​A​, ​M​, ​A​。
   • 我们可以通过深度优先搜索（DFS）或动态规划的方法来查找所有满足条件的路径。
3. 思路：
   • 遍历网格，找到所有字母 Y 的位置。
   • 从每个 Y 开始，尝试通过递归或迭代的方式沿着边相邻的方格寻找符合顺序的字母。
   • 统计符合条件的路径数量。
4. 算法：
   • 使用 深度优先搜索（DFS） 或 动态规划（DP） 递归地遍历网格，计算所有可能的路径。

时间复杂度分析

由于 n ≤ 10 且 ​m ≤ 10​，算法复杂度在最大输入情况下是可以接受的。