A25646. 最多字母路径编程实现有一个 N 行 N 列的网格，网格里的每个格子都有一个字母，每个字母只能是 p、y、t、h、o、n 中的字母。一台机器人按照以下规则移动：1、起始位置可以选择网格中任意一个格子，起始位置的字母不一定为 p；2、每次只能向上下左右相邻的任意一个格子移动一格，并且经过的格子不能再次经过；3、每次移动的格子中的字母必须按照以下环形的顺序，如下图所示：例如：当前字母为 t，那么移动的…
题目描述
最多字母路径
编程实现
有一个 N 行 N 列的网格，网格里的每个格子都有一个字母，每个字母只能是 p、y、t、h、o、n 中的字母。
一台机器人按照以下规则移动：
1、起始位置可以选择网格中任意一个格子，起始位置的字母不一定为 p；
2、每次只能向上下左右相邻的任意一个格子移动一格，并且经过的格子不能再次经过；
3、每次移动的格子中的字母必须按照以下环形的顺序，如下图所示：
例如：当前字母为 t，那么移动的下一个格子中的字母必须为 h。
给定 N 行 N 列的网格，请计算机器人最多可以经过多少个字母。
例如：N = 4，4 行 4 列的网格中的字母如左图，可经过最多字母的移动路径如右图：
以第三行第二列的 h 作为起始位置，按照 h→o→n→p→y→t→h 的顺序移动，机器人经过的字母最多，可以经过 7 个字母。
输入描述
第一行输入一个整数 N（2≤N≤50），表示网格的行数和列数
接下来输入 N 行，每行 N 个字母，每个字母只能是 p、y、t、h、o、n 中的字母，字母之间以一个空格隔开
输出描述
输出一个整数，表示机器人最多可以经过多少个字母
样例输入
4
y n p p
t o y t
n h p h
n h o t样例输出
7参考答案
def max_letters_path():
# 定义字母的顺序映射
next_letter = {
'p': 'y',
'y': 't',
't': 'h',
'h': 'o',
'o': 'n',
'n': 'p'
}
N = int(input())
grid = []
for _ in range(N):
row = input().strip().split()
grid.append(row)
# 动态规划表，dp[i][j] 表示从(i,j)出发的最长路径长度
dp = [[0]*N for _ in range(N)]
max_length = 0
# 四个可能的移动方向：上、下、左、右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(i, j):
if dp[i][j] != 0:
return dp[i][j]
current_char = grid[i][j]
next_char = next_letter[current_char]
max_path = 1 # 至少可以访问当前单元格
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < N and 0 <= nj < N and grid[ni][nj] == next_char:
max_path = max(max_path, 1 + dfs(ni, nj))
dp[i][j] = max_path
return max_path
for i in range(N):
for j in range(N):
current_max = dfs(i, j)
if current_max > max_length:
max_length = current_max
print(max_length)
max_letters_path()答案解析
解析
字母顺序映射：使用字典next_letter来定义每个字母的下一个字母，形成环形顺序。
输入处理：读取网格的行数N和网格数据，存储在二维列表grid中。
动态规划表初始化：dp表用于存储从每个单元格出发的最长路径长度，初始值为0。
DFS函数：dfs(i, j)函数使用深度优先搜索来计算从(i, j)出发的最长路径。如果dp[i][j]已经计算过，直接返回结果；否则，检查四个方向的相邻单元格，如果相邻单元格的字母是当前字母的下一个字母，则递归计算路径长度。
遍历所有起点：对网格中的每个单元格调用dfs函数，更新全局最长路径长度max_length。
输出结果：打印最长路径长度。