解题思路

一道非常典型的回溯题目，首先从第一个点出发，作为起始位置进行深度优先遍历（每个非0点都要作为起始位置），在每个dfs中，要判断当前位置是否满足条件，即没有越界或为0或未访问过（也是0），满足条件则相加并更新最大价值，接着从四个方向继续dfs，当然别忘了回溯，因为下一次还可能从该点dfs，代码如下：

代码

class Solution {
private:
    int maxValue = 0;
    int m, n;
    int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        // 遍历每一个非0位置
        for(int i = 0; i < m; i ++) {
            for(int j = 0; j < n; j ++) {
                int cur = 0;
                if(grid[i][j] != 0) {
                    dfs(grid, i, j, cur);
                }
            }
        }
        return maxValue;
    }

    void dfs(vector<vector<int>>& grid, int i , int j, int cur) {
        // 不满足条件就退出dfs
        if(i >= m || i < 0 || j >= n || j < 0 || grid[i][j] == 0) {
            return;
        }
        // 记录当前位置的值，便于回溯
        int temp = grid[i][j];
        cur += temp;
        maxValue = max(maxValue, cur);
        // 标记为不可访问
        grid[i][j] = 0;
        // 从四个方向进行遍历
        for(auto d : direction) {
            dfs(grid, i + d[0], j + d[1], cur);
        }
        // 回溯
        grid[i][j] = temp;
    }

};