Đường đi vàng tối đa trong C++

Cho lưới m×n, mỗi ô chứa lượng vàng (0 = trống). Tìm lượng vàng tối đa có thể thu thập theo quy tắc:

• Thu thập toàn bộ vàng khi đến ô.
• Di chuyển 4 hướng (trên, dưới, trái, phải).
• Không được vào lại ô đã đi.
• Không được vào ô có vàng = 0.

Ví dụ: [[0,6,0],[5,8,7],[0,9,0]] → 24 (đường đi 9→8→7).

Thuật toán giải quyết (DFS + Backtracking)

1. Hàm dfs(grid, n, m, i, j):
   • Nếu ngoài biên hoặc ô = 0 hoặc đã thăm (đánh dấu -1) → trả về 0.
   • Lưu giá trị ô, đánh dấu -1.
   • Gọi đệ quy 4 hướng, lấy max.
   • Khôi phục giá trị ô (backtrack).
   • Trả về vàng tại ô + max từ 4 hướng.
2. Duyệt mọi ô làm điểm xuất phát, lấy max kết quả.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int dfs(vector<vector<int>>& grid, int n, int m, int i, int j) {
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] <= 0) return 0;
        int val = grid[i][j];
        grid[i][j] = -1;
        int best = max({dfs(grid,n,m,i+1,j), dfs(grid,n,m,i-1,j),
                        dfs(grid,n,m,i,j+1), dfs(grid,n,m,i,j-1)});
        grid[i][j] = val;
        return val + best;
    }
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(), ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] > 0)
                    ans = max(ans, dfs(grid, n, m, i, j));
        return ans;
    }
};

int main() {
    vector<vector<int>> v = {{0,6,0},{5,8,7},{0,9,0}};
    Solution ob;
    cout << ob.getMaximumGold(v);
}

Đầu vào

[[0,6,0],[5,8,7],[0,9,0]]

Đầu ra

24