Leet Code Daily 2024-05-14 - Path with Maximum Gold

vector<pair<int, int>> kDir = {
    { -1,  0 },
    { +1,  0 },
    {  0, -1 },
    {  0, +1 },
};

class Solution {
public:

    int ans = 0;

    void dfs(vector<vector<int>>& grid, int x, int y, int gold) {
        ans = max(ans, gold);
        for (const auto &d : kDir) {
            int nx = x + d.first;
            int ny = y + d.second;
            if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size()) {
                int current = grid[nx][ny];
                if (current > 0) {
                    grid[nx][ny] = 0;
                    dfs(grid, nx, ny, gold + current);
                    grid[nx][ny] = current;
                }
            }
        }
    }

    int getMaximumGold(vector<vector<int>>& grid) {
        for (int x = 0; x < grid.size(); x++) {
            for (int y = 0; y < grid[0].size(); y++) {
                int current = grid[x][y];
                if (current > 0) {
                    grid[x][y] = 0;
                    dfs(grid, x, y, current);
                    grid[x][y] = current;
                }
            }
        }
        return ans;
    }
};