1219. Path with Maximum Gold

问题:

给定一个二维数组表示藏金矿地图,每个cell表示所在位置藏有的金矿量,

求从任意一个cell开始走地图,不走走过的cell,不走金矿量=0的cell,只能从当前cell的上下左右四个方向进行下一步移动。

最终能获得的最大金矿量。

Example 1:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

Example 2:
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
 
Constraints:
1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
There are at most 25 cells containing gold.

  

解法:Backtracking(回溯算法)

状态:走到当前位置(i,j)所获得的金矿量path,和标记了已经走过的路径visited。

选择:上下左右四个方向:除去:超过边界 || 已经走过visited=true || 金矿为0grid[i][j]=0

退出递归条件:当前位置不可走,满足

上一篇:26. 删除有序数组中的重复项


下一篇:Acwing---1219. 移动距离 (Java)_蓝桥杯题