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。

自建示例

一条弯曲路径可以收集全部黄金:

输入: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 的格子作为起点并立即结束即可。