列表

详情

675. 为高尔夫比赛砍树

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：

每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。

你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

 

示例 1：

输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。

示例 2：

输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
输出：-1
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。

示例 3：

输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
输出：6
解释：可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int cutOffTree(vector<vector<int>>& forest) { } };

javascript 解法, 执行用时: 940 ms, 内存消耗: 50.4 MB, 提交时间: 2023-06-09 15:42:25 

const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];

/**
 * @param {number[][]} forest
 * @return {number}
 */
var cutOffTree = function(forest) {
    const trees = [];
    const row = forest.length;
    const col = forest[0].length;
    for (let i = 0; i < row; ++i) {
        for (let j = 0; j < col; ++j) {
            if (forest[i][j] > 1) {
                trees.push([i, j]);
            }
        }
    }
    trees.sort((a, b) => forest[a[0]][a[1]] - forest[b[0]][b[1]]);

    let cx = 0;
    let cy = 0;
    let ans = 0;
    for (let i = 0; i < trees.length; ++i) {
        let steps = bfs(forest, cx, cy, trees[i][0], trees[i][1]);
        if (steps === -1) {
            return -1;
        }
        ans += steps;
        cx = trees[i][0];
        cy = trees[i][1];
    }
    return ans;
};

const bfs = (forest, sx, sy, tx, ty) => {
    if (sx === tx && sy === ty) {
        return 0;
    }

    const row = forest.length;
    const col = forest[0].length;
    let step = 0;
    const queue = [];
    const visited = new Array(row).fill(0).map(() => new Array(col).fill(0));
    queue.push([sx, sy]);
    visited[sx][sy] = true;
    while (queue.length) {
        step++;
        const sz = queue.length;
        for (let i = 0; i < sz; ++i) {
            const cell = queue.shift();
            const cx = cell[0], cy = cell[1];
            for (let j = 0; j < 4; ++j) {
                const nx = cx + dirs[j][0];
                const ny = cy + dirs[j][1];
                if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
                    if (!visited[nx][ny] && forest[nx][ny] > 0) {
                        if (nx === tx && ny === ty) {
                            return step;
                        }
                        queue.push([nx, ny]);
                        visited[nx][ny] = true;
                    }
                }
            }
        }
    }
    return -1;
}

golang 解法, 执行用时: 236 ms, 内存消耗: 7.8 MB, 提交时间: 2023-06-09 15:41:52 

// bfs
var dir4 = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func cutOffTree(forest [][]int) (ans int) {
    type pair struct{ dis, x, y int }
    trees := []pair{}
    for i, row := range forest {
        for j, h := range row {
            if h > 1 {
                trees = append(trees, pair{h, i, j})
            }
        }
    }
    sort.Slice(trees, func(i, j int) bool { return trees[i].dis < trees[j].dis })

    bfs := func(sx, sy, tx, ty int) int {
        m, n := len(forest), len(forest[0])
        vis := make([][]bool, m)
        for i := range vis {
            vis[i] = make([]bool, n)
        }
        vis[sx][sy] = true
        q := []pair{{0, sx, sy}}
        for len(q) > 0 {
            p := q[0]
            q = q[1:]
            if p.x == tx && p.y == ty {
                return p.dis
            }
            for _, d := range dir4 {
                if x, y := p.x+d.x, p.y+d.y; 0 <= x && x < m && 0 <= y && y < n && !vis[x][y] && forest[x][y] > 0 {
                    vis[x][y] = true
                    q = append(q, pair{p.dis + 1, x, y})
                }
            }
        }
        return -1
    }

    preX, preY := 0, 0
    for _, t := range trees {
        d := bfs(preX, preY, t.x, t.y)
        if d < 0 {
            return -1
        }
        ans += d
        preX, preY = t.x, t.y
    }
    return
}

java 解法, 执行用时: 862 ms, 内存消耗: 43 MB, 提交时间: 2023-06-09 15:41:18 

class Solution {
    int N = 50;
    int[][] g = new int[N][N];
    int n, m;
    int[] p = new int[N * N + 10];
    List<int[]> list = new ArrayList<>();
    void union(int a, int b) {
        p[find(a)] = p[find(b)];
    }
    boolean query(int a, int b) {
        return find(a) == find(b);
    }
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    int getIdx(int x, int y) {
        return x * m + y;
    }
    public int cutOffTree(List<List<Integer>> forest) {
        n = forest.size(); m = forest.get(0).size();
        // 预处理过程中，同时使用「并查集」维护连通性
        for (int i = 0; i < n * m; i++) p[i] = i;
        int[][] tempDirs = new int[][]{{0,-1},{-1,0}};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = forest.get(i).get(j);
                if (g[i][j] > 1) list.add(new int[]{g[i][j], i, j});
                if (g[i][j] == 0) continue;
                // 只与左方和上方的区域联通即可确保不重不漏
                for (int[] di : tempDirs) {
                    int nx = i + di[0], ny = j + di[1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (g[nx][ny] != 0) union(getIdx(i, j), getIdx(nx, ny));
                }
            }
        }
        // 若不满足所有树点均与 (0,0)，提前返回无解
        for (int[] info : list) {
            int x = info[1], y = info[2];
            if (!query(getIdx(0, 0), getIdx(x, y))) return -1;
        }
        Collections.sort(list, (a,b)->a[0]-b[0]);
        int x = 0, y = 0, ans = 0;
        for (int[] ne : list) {
            int nx = ne[1], ny = ne[2];
            int d = astar(x, y, nx, ny);
            if (d == -1) return -1;
            ans += d;
            x = nx; y = ny;
        }
        return ans;
    }
    int f(int X, int Y, int P, int Q) {
        return Math.abs(X - P) + Math.abs(Y - Q);
    }
    int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    int astar(int X, int Y, int P, int Q) {
        if (X == P && Y == Q) return 0;
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]);
        q.add(new int[]{f(X, Y, P, Q), X, Y});
        map.put(getIdx(X, Y), 0);
        while (!q.isEmpty()) {
            int[] info = q.poll();
            int x = info[1], y = info[2], step = map.get(getIdx(x, y));
            for (int[] di : dirs) {
                int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny);
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (g[nx][ny] == 0) continue;
                if (nx == P && ny == Q) return step + 1;
                if (!map.containsKey(nidx) || map.get(nidx) > step + 1) {
                    q.add(new int[]{step + 1 + f(nx, ny, P, Q), nx, ny});
                    map.put(nidx, step + 1);
                }
            }
        }
        return -1;
    }
}

java 解法, 执行用时: 820 ms, 内存消耗: 43 MB, 提交时间: 2023-06-09 15:40:44 

class Solution {
    int N = 50;
    int[][] g = new int[N][N];
    int n, m;
    public int cutOffTree(List<List<Integer>> forest) {
        n = forest.size(); m = forest.get(0).size();
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = forest.get(i).get(j);
                if (g[i][j] > 1) list.add(new int[]{g[i][j], i, j});
            }
        }
        Collections.sort(list, (a,b)->a[0]-b[0]);
        int x = 0, y = 0, ans = 0;
        for (int[] ne : list) {
            int nx = ne[1], ny = ne[2];
            int d = astar(x, y, nx, ny);
            if (d == -1) return -1;
            ans += d;
            x = nx; y = ny;
        }
        return ans;
    }
    int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    int getIdx(int x, int y) {
        return x * m + y;
    }
    int f(int X, int Y, int P, int Q) {
        return Math.abs(X - P) + Math.abs(Y - Q);
    }
    int astar(int X, int Y, int P, int Q) {
        if (X == P && Y == Q) return 0;
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]);
        q.add(new int[]{f(X, Y, P, Q), X, Y});
        map.put(getIdx(X, Y), 0);
        while (!q.isEmpty()) {
            int[] info = q.poll();
            int x = info[1], y = info[2], step = map.get(getIdx(x, y));
            for (int[] di : dirs) {
                int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny);
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (g[nx][ny] == 0) continue;
                if (nx == P && ny == Q) return step + 1;
                if (!map.containsKey(nidx) || map.get(nidx) > step + 1) {
                    q.add(new int[]{step + 1 + f(nx, ny, P, Q), nx, ny});
                    map.put(nidx, step + 1);
                }
            }
        }
        return -1;
    }
}

java 解法, 执行用时: 344 ms, 内存消耗: 42.8 MB, 提交时间: 2023-06-09 15:40:13 

// bfs
class Solution {
    int N = 50;
    int[][] g = new int[N][N];
    int n, m;
    public int cutOffTree(List<List<Integer>> forest) {
        n = forest.size(); m = forest.get(0).size();
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = forest.get(i).get(j);
                if (g[i][j] > 1) list.add(new int[]{g[i][j], i, j});
            }
        }
        Collections.sort(list, (a,b)->a[0]-b[0]);
        int x = 0, y = 0, ans = 0;
        for (int[] ne : list) {
            int nx = ne[1], ny = ne[2];
            int d = bfs(x, y, nx, ny);
            if (d == -1) return -1;
            ans += d;
            x = nx; y = ny;
        }
        return ans;
    }
    int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    int bfs(int X, int Y, int P, int Q) {
        if (X == P && Y == Q) return 0;
        boolean[][] vis = new boolean[n][m];
        Deque<int[]> d = new ArrayDeque<>();
        d.addLast(new int[]{X, Y});
        vis[X][Y] = true;
        int ans = 0;
        while (!d.isEmpty()) {
            int size = d.size();
            while (size-- > 0) {
                int[] info = d.pollFirst();
                int x = info[0], y = info[1];
                for (int[] di : dirs) {
                    int nx = x + di[0], ny = y + di[1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (g[nx][ny] == 0 || vis[nx][ny]) continue;
                    if (nx == P && ny == Q) return ans + 1;
                    d.addLast(new int[]{nx, ny});
                    vis[nx][ny] = true;
                }
            }
            ans++;
        }
        return -1;
    }
}

python3 解法, 执行用时: 6620 ms, 内存消耗: 16.4 MB, 提交时间: 2023-06-09 15:38:54 

# bfs方法，每次都求从当前最矮的树到次矮的树的最小距离，最后累加答案即可。
DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)
class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        m, n = len(forest), len(forest[0])
        trees = sorted((forest[i][j], i, j) for i, j in product(range(m), range(n)) if forest[i][j] > 1)

        def bfs(start, end):
            queue = deque([(start, 0)])
            explored = [list(r) for r in forest]
            while queue:
                cur, cost = queue.popleft()
                if cur == end:
                    return cost
                x, y = cur
                cost += 1
                for dx, dy in DIRS:
                    if 0 <= (nx := x + dx) < m and 0 <= (ny := y + dy) < n and explored[nx][ny]:
                        explored[nx][ny] = 0
                        queue.append(((nx, ny), cost))
            return -1
        
        ans = bfs((0, 0), trees[0][1:])
        for a, b in pairwise(trees):
            if (res := bfs(a[1:], b[1:])) == -1:
                return -1
            ans += res
        return ans

上一题

© 2024 leetcode.cn