1219

// class Solution {
// public:
// int f(int i, int j, vector<vector<int>>& g, vector<vector<int>>& dp, vector<vector<int>>& vis) {
//     int n = g.size();
//     int m = g[0].size();

//     if (i < 0 || j < 0 || i >= n || j >= m || g[i][j] == 0 || vis[i][j] == 1)
//         return 0;

//     if (dp[i][j] != -1)
//         return dp[i][j];

//     vis[i][j] = 1;

//     int a = f(i + 1, j, g, dp, vis) + g[i][j];
//     int b = f(i, j + 1, g, dp, vis) + g[i][j];
//     int c = f(i, j - 1, g, dp, vis) + g[i][j];
//     int d = f(i - 1, j, g, dp, vis) + g[i][j];

//     dp[i][j] = max({a, b, c, d});
//     vis[i][j] = 0; // Unmarking visited cell

//     return dp[i][j];
// }

// int getMaximumGold(vector<vector<int>>& g) {
//     int ans = 0;
//     int n = g.size();
//     int m = g[0].size();
    
//     for (int i = 0; i < n; i++) {
//         for (int j = 0; j < m; j++) {
//             vector<vector<int>> vis(n, vector<int>(m, 0));
//             vector<vector<int>> dp(n, vector<int>(m, -1));

//             ans = max(ans, f(i, j, g, dp, vis));
//         }
//     }
//     return ans;
// }
// };


class Solution {
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        int maxGold = 0;

        // Search for the path with the maximum gold starting from each cell
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                maxGold =
                    max(maxGold, dfsBacktrack(grid, rows, cols, row, col));
            }
        }
        return maxGold;
    }

private:
    const vector<int> DIRECTIONS = {0, 1, 0, -1, 0};

    int dfsBacktrack(vector<vector<int>>& grid, int rows, int cols, int row,
                     int col) {
        // Base case: this cell is not in the matrix or this cell has no gold
        if (row < 0 || col < 0 || row == rows || col == cols ||
            grid[row][col] == 0) {
            return 0;
        }
        int maxGold = 0;

        // Mark the cell as visited and save the value
        int originalVal = grid[row][col];
        grid[row][col] = 0;

        // Backtrack in each of the four directions
        for (int direction = 0; direction < 4; direction++) {
            maxGold =
                max(maxGold,
                    dfsBacktrack(grid, rows, cols, DIRECTIONS[direction] + row,
                                 DIRECTIONS[direction + 1] + col));
        }

        // Set the cell back to its original value
        grid[row][col] = originalVal;
        return maxGold + originalVal;
    }
};