0675. Cut Off Trees for Golf Event¶
题目信息¶
- 题号:
0675
- 难度:
Hard
- 主题:
网格、障碍物、按高度排序、四方向最短步数
- 原题:
- 重点:
从左上角出发、必须按树高严格递增顺序砍树、只能经过非零格子、砍掉后该格变为可通行地面
题目重述¶
给定 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 的树被零格完全隔离,无法完成全部任务。