PathWithMaxGold

class Solution {
    private int[][] direction = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    int shubh = 0; // Initialize to 0

    public int getMaximumGold(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] vis = new int[n][m]; // Initialize vis array outside the loop

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

        return shubh;
    }

    private void DFS(int[][] grid, int[][] vis, int i, int j, int sum) {
        vis[i][j] = 1;
        sum += grid[i][j];
        shubh = Math.max(shubh, sum);

        for (int k = 0; k < 4; k++) {
            int n_i = i + direction[k][0];
            int n_j = j + direction[k][1];

            if (n_i >= 0 && n_i < grid.length && n_j >= 0 && n_j < grid[0].length && vis[n_i][n_j] == 0 && grid[n_i][n_j] != 0) {
                DFS(grid, vis, n_i, n_j, sum);
            }
        }

        // Revert changes after recursive call
        vis[i][j] = 0;
    }
}