2022-03-24：你被请来给一个要举办高尔夫比赛的树林砍树，树林由一个 m x n 的矩阵表示， 在这个矩阵中： 0 表示障碍，无法触碰 1 表示地面，可以行走 比 1 大的数 表示有树的单元格，

2022-03-24：你被请来给一个要举办高尔夫比赛的树林砍树，树林由一个 m x n 的矩阵表示， 在这个矩阵中：
0 表示障碍，无法触碰
1 表示地面，可以行走
比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，
如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

答案2022-03-24：

时间紧，具体见代码。

代码用golang编写。代码如下：

package mainimport ("fmt""sort"
)func main() {forest := [][]int{{1, 2, 3}, {0, 0, 4}, {7, 6, 5}}ret := cutOffTree(forest)fmt.Println(ret)
}func cutOffTree(forest [][]int) int {n := len(forest)m := len(forest[0])// [ [3,5,2], [1,9,4] , [2,6,10] ]// 低 中 高cells := make([][]int, 0)for i := 0; i < n; i++ {for j := 0; j < m; j++ {val := forest[i][j]if val > 1 {cells = append(cells, []int{i, j, val})}}}sort.Slice(cells, func(i, j int) bool {a := cells[i]b := cells[j]return a[2] < b[2]})ans := 0lastR := 0lastC := 0for _, cell := range cells {step := bestWalk(forest, lastR, lastC, cell[0], cell[1])if step == -1 {return -1}ans += steplastR = cell[0]lastC = cell[1]forest[lastR][lastC] = 1}return ans
}var next = []int{-1, 0, 1, 0, -1}// 0 1 2 3 4
// i
// 行 + next[i-1]
// 列 + next[i]
// i == 1 -> 上
// i == 2 -> 右
// i == 3 -> 下
// i == 4 -> 左
func bestWalk(forest [][]int, sr, sc, tr, tc int) int {n := len(forest)m := len(forest[0])seen := make([][]bool, n)for i := 0; i < n; i++ {seen[i] = make([]bool, n)}//LinkedList<int[]> deque = new LinkedList<>();deque := make([][]int, 0)deque = append(deque, []int{0, sr, sc})deque = append([][]int{{0, sr, sc}}, deque...)for len(deque) > 0 {cur := deque[0]deque = deque[1:]step := cur[0]r := cur[1]c := cur[2]if r == tr && c == tc {return step}seen[r][c] = truefor i := 1; i < 5; i++ { // (r,c) 上下左右，全试试！nr := r + next[i-1]nc := c + next[i]if nr >= 0 && nr < n && nc >= 0 && nc < m && !seen[nr][nc] && forest[nr][nc] > 0 {move := []int{step + 1, nr, nc}// 更近的话if (i == 1 && r > tr) || (i == 2 && c < tc) || (i == 3 && r < tr) || (i == 4 && c > tc) {deque = append([][]int{move}, deque...)} else { // 更远的话，放到尾部！deque = append(deque, move)}}}}return -1
}

执行结果如下：

左神java代码