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 }
