你被请来给一个要举办高尔夫比赛的树林砍树,树林由一个 m x n 的矩阵表示, 在这个矩阵中: 0 表示障碍,无法触碰 1 表示地面,可以行走 比 1 大的数 表示有树的单元格
  KRe60ogUm4le 18天前 69 0

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

时间紧,具体见代码。

代码用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
}

执行结果如下:

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

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 18天前 0

暂无评论

推荐阅读
KRe60ogUm4le
最新推荐 更多

2024-05-31