Path with Maximum Gold ใน C++: หาทองคำสูงสุดในกริดด้วย DFS

โจทย์

กริด m×n แต่ละเซลล์มีทองคำ (0 = ว่าง) เริ่มที่เซลล์ไหนก็ได้ เดิน 4 ทิศทาง ไม่ซ้ำเซลล์ ไม่เดินเซลล์ 0 หาทองคำสูงสุดที่เก็บได้

ตัวอย่าง: [[0,6,0],[5,8,7],[0,9,0]] → 24 (เส้นทาง 9→8→7)

แนวคิด: DFS + Backtracking

ลองเริ่มจากทุกเซลล์ที่ไม่ใช่ 0 DFS สำรวจ 4 ทิศทาง ทำเครื่องหมาย visited ด้วยการตั้งค่าเป็น -1 แล้วคืนค่าเดิม (backtrack)

ขั้นตอน

1. ฟังก์ชัน dfs(grid, i, j):
   • ถ้าออกนอกกรอบ หรือ grid[i][j] <= 0 → return 0
   • gold = grid[i][j], ตั้ง grid[i][j] = -1 (visited)
   • gold += max(dfs(i+1,j), dfs(i-1,j), dfs(i,j+1), dfs(i,j-1))
   • คืนค่า grid[i][j] = gold (backtrack)
   • return gold
2. ลูปทุกเซลล์ เรียก dfs เก็บค่าสูงสุด

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int i, int j) {
        int n = grid.size(), m = grid[0].size();
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] <= 0) return 0;
        
        int gold = grid[i][j];
        grid[i][j] = -1; // mark visited
        
        gold += max({dfs(grid, i+1, j), dfs(grid, i-1, j), 
                     dfs(grid, i, j+1), dfs(grid, i, j-1)});
        
        grid[i][j] = gold - max({dfs(grid, i+1, j), dfs(grid, i-1, j), 
                                 dfs(grid, i, j+1), dfs(grid, i, j-1)}); // WRONG! 
        // ถูกต้อง: เก็บค่าเดิมไว้ก่อน
        return gold;
    }
    
    // เวอร์ชันถูกต้อง:
    int dfs2(vector<vector<int>>& grid, int i, int j) {
        int n = grid.size(), m = grid[0].size();
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] <= 0) return 0;
        
        int cur = grid[i][j];
        grid[i][j] = -1;
        int best = max({dfs2(grid, i+1, j), dfs2(grid, i-1, j), 
                        dfs2(grid, i, j+1), dfs2(grid, i, j-1)});
        grid[i][j] = cur; // backtrack
        return cur + best;
    }
    
    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, dfs2(grid, i, j));
        return ans;
    }
};

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

อินพุต / เอาต์พุต

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

Output: 24

ความซับซ้อน

• Time: O(m × n × 4^(m×n)) worst case แต่จริงๆ น้อยมากเพราะเซลล์ 0 และ visited จำกัดการขยาย
• Space: O(m × n) recursion stack

หมายเหตุ: โค้ดต้นฉบับมี bug ในการ backtrack (คืนค่า grid ผิด) โค้ดด้านบนแก้ไขแล้ว