โปรแกรมหาเหรียญสูงสุดที่เก็บได้จากเมทริกซ์เดิน 4 ทิศทางใน Python

คำอธิบายโจทย์

ให้เมทริกซ์ 2D ค่า = จำนวนเหรียญ เริ่มที่ตำแหน่งไหนก็ได้ เดิน 4 ทิศทาง (บน ล่าง ซ้าย ขวา) เก็บเหรียญแล้วเซลล์กลายเป็น 0 ไม่สามารถเดินเข้าสู่เซลล์ 0 ได้ หาเหรียญสูงสุดที่เก็บได้

ตัวอย่าง

เมทริกซ์:

วิธีแก้ปัญหา

DFS + Backtracking ลองเริ่มจากทุกเซลล์ที่มีเหรียญ:

1. จากเซลล์ (i,j) ที่มีเหรียญ: เก็บเหรียญ (เซ็ตเป็น 0), เรียก DFS หาเพิ่ม
2. ลองเดิน 4 ทิศทาง เฉพาะเซลล์ที่ valid และมีเหรียญ > 0
3. Backtrack: คืนค่าเหรียญกลับไป
4. ลองทุกจุดเริ่มต้น หาค่าสูงสุด

โค้ด Python

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))

อินพุต

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

เอาต์พุต

18