YF云飞 2023-05-07 16:31 采纳率: 65%
浏览 116
已结题

一道编程算法,不知道哪里出了问题

img

img

img

我的代码如下:


class Solution:
    def extractMantra(self, matrix: List[str], mantra: str) -> int:
        m, n, L = len(matrix), len(matrix[0]), len(mantra)
        pos = {}  # 记录每个字母在矩阵中的所有位置

        for i in range(m):
            for j in range(n):
                c = matrix[i][j]
                if c in pos:
                    pos[c].append((i, j))
                else:
                    pos[c] = [(i, j)]

        MAX = float('inf')
        dp = [[MAX] * n for _ in range(L + 1)]
        for x, y in pos[mantra[0]]:
            dp[1][y] = x  # 初始化第一层状态

        for i in range(2, L + 1):
            for x, y in pos[mantra[i-1]]:
                for prev_x, prev_y in pos[mantra[i-2]]:
                    dp[i][y] = min(dp[i][y], dp[i-1][prev_y] + abs(x-prev_x) + abs(y-prev_y))

        return min(dp[L]) if min(dp[L]) < MAX else -1

img

求正确代码,有偿

  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 已结题 (查看结题原因) 5月7日
    • 赞助了问题酬金15元 5月7日
    • 创建了问题 5月7日