1219. Path with Maximum Gold

解题思路：本题的做法比较简单且直观，遍历给出的金矿矩阵，如果有金子，则依次为起点开始进行dfs，为了节省空间，将访问过的金矿的数量设置为0，当本层的递归结束之后再将它恢复为原来的值。

注意：这道题目不能采用dfs + memorization，因为对于一个固定的点来说，它的终止条件对于不同的起始点是不一样的，例如一个二维的矩阵 [[1, 2], [3, 4]], 如果以1作为开始点，4 的返回值应该为(2, 3)(分别从不同的方向访问4)，可如果从2 开始作为起始点访问，它的值应该是4(1 + 3)。所以在描述中限定了规模为 15 * 15 且最多有25 个金矿。

时间复杂度：假设金矿分布满，每一次的递归有三个不同的选择， 为 O(3 ^ (m * n))

空间复杂度：O(1)

class Solution {
public:
    vector<pair<int, int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int recursive(vector<vector<int>>& grid, int i, int j){
        int goldCnt = grid[i][j];
        int curGold = grid[i][j];
        grid[i][j] = 0;
        for(auto dir : dirs){
            int x = i + dir.first;
            int y = j + dir.second;
            if(0 <= x && x < grid.size() && 0 <= y && y < grid[0].size() && grid[x][y] > 0){
                goldCnt = max(goldCnt, curGold + recursive(grid, x, y));
            }
        }
        grid[i][j] = curGold;
        return goldCnt;
    }
    
    int getMaximumGold(vector<vector<int>>& grid) {
        int maxGold = 0;
        for(int row = 0; row < grid.size(); ++row){
            for(int col = 0; col < grid[0].size(); ++col){
                if(grid[row][col] > 0){
                    maxGold = max(maxGold, recursive(grid, row, col));
                }
            }
        }
        return maxGold;
    }
};