In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.
Return the maximum amount of gold you can collect under the conditions:
0 gold.思路： 找最长路的过程是简单的遍历四个方向做DFS。数据规模比较小，可以直接遍历矩阵，找到不是0的点作为起点做DFS。在每次经过一个节点的时候，把它暂时置为0，表示不能再次经过它，等到递归结束的时候再改成原来的值即可。
class Solution {
public:
int directions[5]={0,1,0,-1,0};
int dfs(int i,int j,vector<vector<int>>& grid){
int tem=grid[i][j];
int x,y,result=0;
grid[i][j]=0;
for(int d=0;d<4;d++){
x=i+directions[d];y=j+directions[d+1];
if(x>=0&&y>=0&&x<grid.size()&&y<grid[0].size()&&grid[x][y])
result=max(grid[x][y]+dfs(x,y,grid),result);
}
grid[i][j]=tem;
return result;
}
int getMaximumGold(vector<vector<int>>& grid) {
int result=0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]>0)
result=max(result,grid[i][j]+dfs(i,j,grid));
}
}
return result;
}
};
原文：https://www.cnblogs.com/rarecu/p/11631919.html