1219. Path with Maximum Gold¶
题目信息¶
- 题号:
1219
- 难度:
Medium
- 主题:
网格、回溯、深度优先搜索
- 原题:
- 重点:
可以从任意含金格开始,只能四向移动到未访问的含金格,每个格子最多经过一次
题目重述¶
给定非负整数网格 grid,正数表示该格子的黄金数量,0 表示不能进入。可以选择任意含金格作为起点,每一步移动到上下左右相邻的含金格。
同一路径中不能重复访问格子,也不能进入值为 0 的格子。路径可以在任意时刻结束,请返回一条合法路径能够收集到的最大黄金总量。
1 <= grid.length, grid[i].length <= 15,0 <= grid[i][j] <= 100,含金格数量不超过 25。
自建示例¶
一条弯曲路径可以收集全部黄金:
输入:grid = [[1,0,7],[2,0,6],[3,4,5]]
输出:28
解释:按 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 行走可访问全部含金格,总和为 28。
只有一个含金格时直接在该格结束:
输入:grid = [[0,0],[0,9]]
输出:9
解释:选择值为 9 的格子作为起点并立即结束即可。