C++初学者不会用C++写,就用python写了段dfs代码
查看原帖
C++初学者不会用C++写,就用python写了段dfs代码
1252609
jinitaimei11楼主2025/2/1 16:08
p = [[0, 1], [1, 0]]
memo = None
def dfs(x1, y1, x2, y2, grid):
    rows, cols = len(grid), len(grid[0])
    if x1 < 0 or x1 >= rows or y1 < 0 or y1 >= cols or x2 < 0 or x2 >= rows or y2 < 0 or y2 >= cols:
        return float('-inf')
    if x1 == rows - 1 and y1 == cols - 1 and x2 == rows - 1 and y2 == cols - 1:
        return grid[x1][y1]
    if memo[x1][y1][x2][y2] != -1:
        return memo[x1][y1][x2][y2]
    if x1 == x2 and y1 == y2:
        cur_score = grid[x1][y1]
    else:
        cur_score = grid[x1][y1] + grid[x2][y2]
    max_next_score = float('-inf')
    for dx1, dy1 in p:
        for dx2, dy2 in p:
            new_x1, new_y1 = x1 + dx1, y1 + dy1
            new_x2, new_y2 = x2 + dx2, y2 + dy2
            next_score = dfs(new_x1, new_y1, new_x2, new_y2, grid)
            max_next_score = max(max_next_score, next_score)
    memo[x1][y1][x2][y2] = cur_score + max_next_score
    return memo[x1][y1][x2][y2]
m, n = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(m)]
memo = [[[[-1] * n for _ in range(m)] for _ in range(n)] for _ in range(m)]
result = dfs(0, 0, 0, 0, grid)
print(result)

敢不敢把你的python代码拿出来比较?

2025/2/1 16:08
加载中...