0675. Cut Off Trees for Golf Event

题目信息

题号:

0675

难度:

Hard

主题:

网格、障碍物、按高度排序、四方向最短步数

原题:

LeetCode 0675

重点:

从左上角出发、必须按树高严格递增顺序砍树、只能经过非零格子、砍掉后该格变为可通行地面

题目重述

给定 m × n 整数矩阵 forest:值 0 表示不可通行的障碍,值 1 表示普通地面,大于 1 的值表示一棵树及其高度。你从 (0,0) 出发,每一步可以向上下左右相邻的非零格子移动。

必须按照树高从低到高依次走到每棵树所在格并将其砍掉;树高互不相同,砍掉后该格值变为 1,仍可继续通行。返回完成全部砍树所需的最少步数;若某棵按顺序需要砍的树无法到达,返回 -1。矩阵行列数位于 [1, 50],格子值位于 [0, 10^9]。

自建示例

按高度形成一条可达路径:

输入:forest = [[1,2,3],[0,0,4],[7,6,5]]
输出:6
解释:从起点依次到达高度 2、3、4、5、6、7,每次只移动一步,总计 6 步。

后续树被障碍隔开:

输入:forest = [[1,2,0],[0,0,3]]
输出:-1
解释:高度 2 的树可以到达,但高度 3 的树被零格完全隔离,无法完成全部任务。