Leetcode 1331 Solution

class Solution {
public:
    int findMaxGold(vector<vector<int>>& grid, int i, int j, int m, int n)
    {
        if (grid[i][j] == 0)
            return 0;

        int ans = grid[i][j];
        int orig_gold = grid[i][j];

        grid[i][j] = 0;

        int left_max = i > 0 ? findMaxGold(grid, i - 1, j, m, n) : 0;
        int right_max = i < m - 1 ? findMaxGold(grid, i + 1, j, m, n) : 0;
        int up_max = j > 0 ? findMaxGold(grid, i, j - 1, m, n) : 0;
        int down_max = j < n - 1 ? findMaxGold(grid, i, j + 1, m, n) : 0;

        grid[i][j] = orig_gold;
        return ans + std::max(std::max(left_max, right_max), std::max(up_max, down_max));
    }

    int getMaximumGold(vector<vector<int>>& grid) {
        std::vector<std::pair<int, int>> starting_points;

        int m = grid.size();
        int n = grid[0].size();

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j])
                    starting_points.push_back(make_pair(i, j));

        int ans = 0;
        for (auto it = starting_points.begin(); it != starting_points.end(); it++)
        {
            int option = findMaxGold(grid, it->first, it->second, m, n);
            ans = std::max(ans, option);
        }

        return ans;
    }
};