Leet-Code/1219. Path with Maximum Gold.java at master · Anshika15/Leet-Code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    int max = 0;
    public int getMaximumGold(int[][] grid) {

        int n = grid.length;
        int m = grid[0].length;
        boolean vis[][] = new boolean[n][m];

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(grid[i][j] != 0)
                    dfs(grid, i, j, vis, 0, n, m);
            }
        }

        return max;
    }

    void dfs(int[][] grid, int i, int j, boolean vis[][], int sum, int n, int m)
    {
        if(i < 0 || j < 0 || i >= n || j >= m || vis[i][j] == true || grid[i][j] == 0)
            return;

       // max = Math.max(max, sum);
        sum += grid[i][j];
        vis[i][j] = true;

        dfs(grid, i+1, j, vis, sum, n, m);
        dfs(grid, i-1, j, vis, sum, n, m);
        dfs(grid, i, j+1, vis, sum, n, m);
        dfs(grid, i, j-1, vis, sum, n, m);

        max = Math.max(max, sum);

        sum -= grid[i][j];
        vis[i][j] = false;
    }
}