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;
    }
};
相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
48 0
|
4月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
116 1
|
1月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
1月前
|
算法
树的遍历算法有哪些?
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题;广度优先搜索则在图的最短路径、层次相关的问题中较为常用;而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
40 2
|
2月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
35 2
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
32 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
3月前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
在数据密集型应用中,高效搜索算法至关重要。Trie树(前缀树/字典树)通过优化字符串处理和搜索效率成为理想选择。本文通过Python实战演示Trie树构建与应用,显著提升搜索性能。Trie树利用公共前缀减少查询时间,支持快速插入、删除和搜索。以下为简单示例代码,展示如何构建及使用Trie树进行搜索与前缀匹配,适用于自动补全、拼写检查等场景,助力提升应用性能与用户体验。
71 2
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
35 0
|
2月前
|
存储 算法 Java
数据结构和算法--分段树
数据结构和算法--分段树
25 0