题目标签：Backtracking
可以从任意一个不是0的点，作为开始，所以要包括所有不是0的点 为起点，然后开始 dfs：
如果走出范围了，说明不能再移动了；
走过的点标记为负数；
四个方向中，保留一个 return 回来最大的数字 加入总数继续 return；
具体看code。
Java Solution:
Runtime: 13 ms, faster than 86.24%
Memory Usage: 36.8 MB, less than 100.00%
完成日期：01/29/2020
关键点：dfs
class Solution { public int getMaximumGold(int[][] grid) { int max = 0; for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[i].length; j++) { if(grid[i][j] != 0) max = Math.max(max, dfs(grid, i, j)); } } return max; } private int dfs(int[][] grid, int i, int j) { // cannot move anymore if(i < 0 || j < 0 || i == grid.length || j == grid[0].length || grid[i][j] <= 0 ) return 0; int gold = grid[i][j]; grid[i][j] *= -1; // mark it as used //before going to next one // left int max = dfs(grid, i-1, j); // down max = Math.max(max, dfs(grid, i, j-1)); // right max = Math.max(max, dfs(grid, i+1, j)); // up max = Math.max(max, dfs(grid, i, j+1)); // after gold += max; grid[i][j] *= -1; return gold; } }
参考资料：LeetCode Discuss
LeetCode 题目列表 - LeetCode Questions List
题目来源：https://leetcode.com/
LeetCode 1219. Path with Maximum Gold (黄金矿工)
原文：https://www.cnblogs.com/jimmycheng/p/12334569.html