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