Chương trình tìm số tiền xu tối đa có thể thu thập từ ma trận cho trước trong Python

Cho ma trận 2D, mat[r][c] là số tiền xu. Có thể bắt đầu từ bất kỳ vị trí nào, di chuyển 4 hướng (lên, xuống, trái, phải). Khi đến ô, thu thập tiền xu và ô thành 0. Không thể vào ô có 0 tiền xu. Tìm tối đa tiền xu có thể thu thập.

Ví dụ ma trận 3x3 cho kết quả 18 (đường đi 2→3→6→4→3).

Giải pháp

DFS với backtracking từ mọi ô bắt đầu có tiền xu > 0:

• util(a, b): trả về tối đa tiền xu từ ô (a,b) tiếp tục đi
• Thử 4 hướng, nếu ô hợp lệ và có tiền xu > 0: lưu giá trị, đặt ô = 0, đệ quy, khôi phục ô
• Duyệt mọi ô (i,j) làm điểm bắt đầu, lấy max

Ví dụ minh họa

class Solution:
    def solve(self, mat):
        if not mat:
            return 0
        n, m = len(mat), len(mat[0])
        x, y = [-1, 1, 0, 0], [0, 0, -1, 1]
        def ok(a, b):
            return 0 <= a < n and 0 <= b < m and mat[a][b]
        def util(a, b):
            ret = 0
            for k in range(4):
                t1, t2 = x[k] + a, y[k] + b
                if ok(t1, t2):
                    t, mat[t1][t2] = mat[t1][t2], 0
                    ret = max(ret, util(t1, t2) + t)
                    mat[t1][t2] = t
            return ret
        res = 0
        for i in range(n):
            for j in range(m):
                if mat[i][j]:
                    temp, mat[i][j] = mat[i][j], 0
                    res = max(res, util(i, j) + temp)
        return res

ob = Solution()
matrix = [[2, 4, 3], [3, 6, 0], [2, 0, 12]]
print(ob.solve(matrix))

Đầu vào

[[2, 4, 3], [3, 6, 0], [2, 0, 12]]

Đầu ra

18