In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:


	Every time you are located in a cell you will collect all the gold in that cell.
	From your position, you can walk one step to the left, right, up, or down.
	You can't visit the same cell more than once.
	Never visit a cell with 0 gold.
	You can start and stop collecting gold from any position in the grid that has some gold.


&nbsp;
Example 1:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -&gt; 8 -&gt; 7.


Example 2:

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; 6 -&gt; 7.


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 15
	0 &lt;= grid[i][j] &lt;= 100
	There are at most 25 cells containing gold.


class Solution:
    def getMaximumGold(self, grid):
        answer = [0]

        def visit(visited, i, j, gold_sum):
            val = grid[i][j]
            if val == 0 or (i,j) in visited:
                answer[0] = max(answer[0], gold_sum)
                return

            gold_sum_new = gold_sum + val
            visited_new = visited.union({(i,j)})

            if i > 0:
                visit(visited_new, i-1, j, gold_sum_new)

            if j < len(grid[i]) - 1:
                visit(visited_new, i, j+1, gold_sum_new)

            if i < len(grid) - 1:
                visit(visited_new, i+1, j, gold_sum_new)
            if j > 0:
                visit(visited_new, i, j-1, gold_sum_new)
        #choosing the starting points
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] != 0:
                    count = 0

                    try:
                        if grid[i-1][j] != 0:
                            count += 1
                    except:
                        pass
                    try:
                        if grid[i][j+1] != 0:
                            count += 1
                    except:
                        pass
                    try:
                        if grid[i+1][j] != 0:
                            count += 1
                    except:
                        pass
                    try:
                        if grid[i][j-1] != 0:
                            count += 1
                    except:
                        pass

                    if count < 3:
                        visit(set(),i,j,0)

        return answer[0]
class Solution {
    int r = 0;
    int c = 0;
    int max = 0;
    public int getMaximumGold(int[][] grid) {
        r = grid.length;
        c = grid[0].length;
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                if(grid[i][j] != 0) {
                    dfs(grid, i, j, 0);
                }
            }
        }
        return max;
    }
    
    private void dfs(int[][] grid, int i, int j, int cur) {
        if(i < 0 || i >= r || j < 0 || j >= c || grid[i][j] == 0) {
            max = Math.max(max, cur);
            return;
        }
        int val = grid[i][j];
        grid[i][j] = 0;
        dfs(grid, i + 1, j, cur + val);
        dfs(grid, i - 1, j, cur + val);
        dfs(grid, i, j + 1, cur + val);
        dfs(grid, i, j - 1, cur + val);
        grid[i][j] = val;
    }
}
class Solution {
public:
    int maxgold=0;
    int m,n;
    void gold(int i,int j,vector<vector<int>>& grid,vector<vector<int>>& vis,int count){
// Down
        if(i+1<m && !vis[i+1][j] && grid[i+1][j]){
            vis[i][j]=1;
            gold(i+1,j,grid,vis,count+grid[i+1][j]);
            vis[i][j]=0;
        }
// Left
        if(j-1>=0 && !vis[i][j-1] && grid[i][j-1]){
            vis[i][j]=1;
            gold(i,j-1,grid,vis,count+grid[i][j-1]);
            vis[i][j]=0;
        }
// Right
        if(j+1<n && !vis[i][j+1] && grid[i][j+1]){
            vis[i][j]=1;
            gold(i,j+1,grid,vis,count+grid[i][j+1]);
            vis[i][j]=0;
        }
// Up
        if(i-1>=0 && !vis[i-1][j] && grid[i-1][j]){
            vis[i][j]=1;
            gold(i-1,j,grid,vis,count+grid[i-1][j]);
            vis[i][j]=0;
        }
        maxgold=max(maxgold,count);
    }

    int getMaximumGold(vector<vector<int>>& grid) {
        m=grid.size();
        n=grid[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]){
                    vector<vector<int>>vis(m,vector<int>(n,0));
                    gold(i,j,grid,vis,grid[i][j]);
                }
            }
        }
        return maxgold;
    }
};
var getMaximumGold = function(grid) {
    let max = 0;
    
	// This is our internal dfs function that will search all possible directions from a cell
    const mine = (x, y, n) => {
	    // We can't mine any gold if the position is out of the grid, or the cell doesnt have any gold
        if (x < 0 || y < 0 || x > grid.length - 1 || y > grid[x].length - 1 || grid[x][y] == 0) return 0;
		
		// Save the temp value so we can mark the cell as visited
        let temp = grid[x][y];
        grid[x][y] = 0;
        
		// Try mining left, right, up, and down from the current position, 
		// bringing along the gold total that was found in the current cell
        mine(x + 1, y, n + temp);
        mine(x - 1, y, n + temp);
        mine(x, y + 1, n + temp);
        mine(x, y - 1, n + temp);
        
		// After we've tried all directions reset cell to have its original value,
		// so it can be mined from a different starting point
        grid[x][y] = temp;
        
		// Update the max based on the mining done up until the current cell
        max = Math.max(max, n + temp);
    }
	
	// We need to run this dfs function through every potential starting point
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            mine(i, j, 0);
        }
    }
    return max;
    
};
Path with Maximum Gold