2022-03-24：你被请来给一个要举办高尔夫比赛的树林砍树，树林由一个 m x n 的矩阵表

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

答案2022-03-24：

时间紧，具体见代码。

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

package main

import (
	"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 := 0
	lastR := 0
	lastC := 0
	for _, cell := range cells {
		step := bestWalk(forest, lastR, lastC, cell[0], cell[1])
		if step == -1 {
			return -1
		}
		ans += step
		lastR = 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] = true
		for 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代码