golang力扣leetcode 675.为高尔夫比赛砍树

• 675.为高尔夫比赛砍树
• 题解
• 代码

675.为高尔夫比赛砍树

题目：给一个二维矩阵，0不能走，1是陆地，2+是树，1和1往上都能走，从0，0开始，但是要从低树走到高树，计算步数。
举个例子，先从0,0走到最低的树，即<0,1>高为2的树，再走到下一个最低的树，计算步数，如果某棵树走不到则返回-1，反则返回累加步数

[1,2,3]
[0,0,4]
[7,6,5]

思路：
题目蛮简单的，只不过题目描述太恶心了，做阅读理解一样

重点：从低树走高树
1. 将所有树找出来，从小到大排序
2. <0，0>与第一个树计算bfs，第一个树与第二个数计算bfs...
3. bfs:最短路径

func cutOffTree(forest [][]int) int {
	type point struct{ x, y int }
	type pair struct{ x, y, step int }
	n, m := len(forest), len(forest[0])
	dirs := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

	var bfs func(sx, sy, ex, ey int) int
	bfs = func(sx, sy, ex, ey int) int {
		vis := map[point]bool{point{sx, sy}: true}
		queue := []pair{{sx, sy, 0}}
		for len(queue) > 0 {
			tx, ty, step := queue[0].x, queue[0].y, queue[0].step
			queue = queue[1:]
			if tx == ex && ty == ey {
				return step
			}
			for _, v := range dirs {
				nx, ny := tx+v[0], ty+v[1]
				p := pair{nx, ny, step + 1}
				if p.x >= 0 && p.y >= 0 && p.x < n && p.y < m && !vis[point{p.x, p.y}] && forest[p.x][p.y] > 0 {
					queue = append(queue, p)
					vis[point{p.x, p.y}] = true
				}
			}
		}
		return -1
	}
	var tree []pair
	for i, v := range forest {
		for j, vv := range v {
			if vv > 1 {
				tree = append(tree, pair{i, j, vv})
			}
		}
	}
	sort.Slice(tree, func(i, j int) bool {
		return tree[i].step < tree[j].step
	})
	ans, px, py := 0, 0, 0
	for _, v := range tree {
		step := bfs(px, py, v.x, v.y)
		if step == -1 {
			return -1
		}
		ans += step
		px, py = v.x, v.y
	}
	return ans
}