# Leetcode 1331 Solution

https://leetcode.com/problems/path-with-maximum-gold

## 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.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;
}
};
``````