leetcode-675:为高尔夫比赛砍树 (最短路径算法bfs,dijkstra,A*)

简介: leetcode-675:为高尔夫比赛砍树 (最短路径算法bfs,dijkstra,A*)

题目

题目连接

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

0 表示障碍,无法触碰

1 表示地面,可以行走

比 1 大的数 表示有树的单元格,可以行走,数值表示树的高度

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

你需要按照树的高度从低向高砍掉所有的树,每砍过一颗树,该单元格的值变为 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) 位置的树,可以直接砍去,不用算步数。

解题

参考链接

方法一:bfs

可以将树从低到高排序,这样就这样每次要走的,起始点和目的点

然后求起始点和目的点最短路径(bfs)即可

所有最短路径之和就是结果

class Solution {
public:
    int m,n;
    vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}};
    int bfs(vector<vector<int>>& forest,int srcx,int srcy,int dstx,int dsty){
        if(srcx==dstx&&srcy==dsty) return 0;
        queue<pair<int,int>> q;
        q.emplace(srcx,srcy);
        vector<vector<bool>> visited(m,vector<bool>(n,false));
        visited[srcx][srcy]=true;
        int depth=0;
        while(!q.empty()){
            int l=q.size();
            while(l--){
                auto [x,y]=q.front();
                q.pop();
                // visited[x][y]=true;//出队的时候才标记,可能会导致重复入队
                if(x==dstx&&y==dsty){
                    return depth;
                }
                for(vector<int>& dir:dirs){
                    int nx=x+dir[0];
                    int ny=y+dir[1];
                    if(nx<0||nx>=m||ny<0||ny>=n||forest[nx][ny]==0||visited[nx][ny]) continue;
                    q.emplace(nx,ny);
                    visited[nx][ny]=true;
                }
            }
            depth++;  
        }
        return -1;
    }
    int cutOffTree(vector<vector<int>>& forest) {
        m=forest.size(),n=forest[0].size();
        vector<pair<int,int>> paths;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(forest[i][j]>=2){
                    paths.emplace_back(i,j);
                }
            }
        }
        sort(paths.begin(),paths.end(),[&](pair<int,int>&a,pair<int,int>&b){
            return forest[a.first][a.second]<forest[b.first][b.second];
        });
        int res=0;
        int srcx=0,srcy=0;
        for(int i=0;i<paths.size();i++){
            auto [dstx,dsty]=paths[i];
            int step=bfs(forest,srcx,srcy,dstx,dsty);
            if(step==-1) return -1;
            res+=step;
            srcx=dstx;
            srcy=dsty;
        }
        return res;
    }
};

方法二:Dijkstra 算法

也是采用bfs的方法,只不过用【优化队列,每次取出路径最小(把 pair(路径,idx),放入优先队列即可)】的方法, 来取代方法一中的,【层次遍历+每层路径+1】的方法。

在性能上,与方法一来说,其实差不多的

方法三:A* 启发式搜索算法

与Dijstra基本上是一样的,但是 额外记录一个cost,通过优先队列,每次选取cost小的

class Solution {
public:
    int m,n;
    int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    int bfs(vector<vector<int>>& forest,int srcx,int srcy,int dstx,int dsty){
        if(srcx==dstx&&srcy==dsty) return 0;
        vector<vector<int>> costed(m,vector<int>(n,INT_MAX));
        costed[srcx][srcy]=abs(dstx-srcx)+abs(dsty-srcy);
        priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<tuple<int,int,int,int>>> q;
        q.emplace(costed[srcx][srcy],0,srcx,srcy);
        while(!q.empty()){
            auto [cost,dist,x,y]=q.top();
            q.pop();
            if(x==dstx&&y==dsty) return dist;
            for(int i=0;i<4;i++){
                int nx=x+dirs[i][0];
                int ny=y+dirs[i][1];
                if(nx<0||nx>=m||ny<0||ny>=n||forest[nx][ny]==0) continue;
                int ncost=dist+abs(nx-dstx)+abs(ny-dsty);
                if(ncost<costed[nx][ny]){
                    q.emplace(ncost,dist+1,nx,ny);
                    costed[nx][ny]=ncost;
                }
            }
        }
        return -1;
    }
    int cutOffTree(vector<vector<int>>& forest) {
        m=forest.size(),n=forest[0].size();
        vector<pair<int,int>> paths;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(forest[i][j]>=2){
                    paths.emplace_back(i,j);
                }
            }
        }
        sort(paths.begin(),paths.end(),[&](pair<int,int>&a,pair<int,int>&b){
            return forest[a.first][a.second]<forest[b.first][b.second];
        });
        int res=0;
        int srcx=0,srcy=0;
        for(int i=0;i<paths.size();i++){
            auto [dstx,dsty]=paths[i];
            int step=bfs(forest,srcx,srcy,dstx,dsty);
            if(step==-1) return -1;
            res+=step;
            srcx=dstx;
            srcy=dsty;
        }
        return res;
    }
};
相关文章
|
19天前
|
算法 编译器 C++
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
|
4天前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
27 3
 算法系列之数据结构-Huffman树
|
5月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
135 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
19天前
|
存储 算法
算法系列之搜索算法-广度优先搜索BFS
广度优先搜索(BFS)是一种非常强大的算法,特别适用于解决最短路径、层次遍历和连通性问题。在面试中,掌握BFS的基本实现和应用场景,能够帮助你高效解决许多与图或树相关的问题。
32 1
算法系列之搜索算法-广度优先搜索BFS
|
19天前
|
存储 算法 测试技术
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
60 2
|
4月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
4月前
|
算法
树的遍历算法有哪些?
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题;广度优先搜索则在图的最短路径、层次相关的问题中较为常用;而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
68 2
|
5月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
54 2
|
5月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
48 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)