问题:
给定一个二维数组表示藏金矿地图,每个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
退出递归条件:当前位置不可走,满足