蓝桥杯-跳跃


import os
import sys

# 请在此输入您的代码
from math import inf

n, m = map(int, input().split())
grid = []

for _ in range(n):
    grid.append(list(map(int, input().split())))

ans = float(-inf)

def dfs(x, y, tot):
    """
    深度优先搜索从位置 (x, y) 到右下角的所有路径，找出最大价值和
    
    Args:
        x (int): 当前位置的行坐标
        y (int): 当前位置的列坐标
        tot (int): 从起点到当前位置的累计价值和
    
    Returns:
        None: 通过全局变量 ans 记录最大价值
    """
    global ans
    if x == n - 1 and y == m - 1:
        # 到达终点，更新最大值
        ans = max(ans, tot)
        return

    # 枚举移动的可能
    for dx in range(4):
        for dy in range(4):
            # 不能原地动
            if dx == 0 and dy == 0:
                continue
            # 超出移动距离
            if dx + dy > 3:
                continue
            nx, ny = dx + x, dy + y
            if nx < n and ny < m:
                dfs(nx, ny, tot + grid[nx][ny])

dfs(0, 0, grid[0][0])
print(ans)