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;
    }
};
相关文章
|
5天前
|
机器学习/深度学习 数据采集 算法
Python用逻辑回归、决策树、SVM、XGBoost 算法机器学习预测用户信贷行为数据分析报告
Python用逻辑回归、决策树、SVM、XGBoost 算法机器学习预测用户信贷行为数据分析报告
|
2天前
|
机器学习/深度学习 算法 数据处理
探索机器学习中的决策树算法
【5月更文挑战第18天】探索机器学习中的决策树算法,一种基于树形结构的监督学习,常用于分类和回归。算法通过递归划分数据,选择最优特征以提高子集纯净度。优点包括直观、高效、健壮和可解释,但易过拟合、对连续数据处理不佳且不稳定。广泛应用于信贷风险评估、医疗诊断和商品推荐等领域。优化方法包括集成学习、特征工程、剪枝策略和参数调优。
|
5天前
|
机器学习/深度学习 算法
理解并应用机器学习算法:决策树
【5月更文挑战第12天】决策树是直观的分类与回归机器学习算法,通过树状结构模拟决策过程。每个内部节点代表特征属性,分支代表属性取值,叶子节点代表类别。构建过程包括特征选择(如信息增益、基尼指数等)、决策树生成和剪枝(预剪枝和后剪枝)以防止过拟合。广泛应用在信贷风险评估、医疗诊断等领域。理解并掌握决策树有助于解决实际问题。
|
5天前
|
存储 缓存 算法
数据结构与算法 树(B树,B+树,红黑树待完善)
数据结构与算法 树(B树,B+树,红黑树待完善)
19 0
|
5天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
9 0
|
5天前
|
算法 机器人 Python
Python实现教程:平面最短路径算法
Python实现教程:平面最短路径算法
15 1
|
5天前
|
存储 算法
Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组
给定一个无序整数数组和目标值,找出数组中和为目标值的两个数的下标。要求不重复且可按任意顺序返回。示例:输入nums = [2,7,11,15], target = 9,输出[0,1]。暴力解法时间复杂度O(n²),优化解法利用哈希表实现,时间复杂度O(n)。
22 0
|
5天前
|
机器学习/深度学习 算法 数据可视化
Matlab决策树、模糊C-均值聚类算法分析高校教师职称学历评分可视化
Matlab决策树、模糊C-均值聚类算法分析高校教师职称学历评分可视化
|
5天前
|
机器学习/深度学习 算法 数据可视化
【Python机器学习专栏】决策树算法的实现与解释
【4月更文挑战第30天】本文探讨了决策树算法,一种流行的监督学习方法,用于分类和回归。文章阐述了决策树的基本原理,其中内部节点代表特征判断,分支表示判断结果,叶节点代表类别。信息增益等标准用于衡量特征重要性。通过Python的scikit-learn库展示了构建鸢尾花数据集分类器的示例,包括训练、预测、评估和可视化决策树。最后,讨论了模型解释和特征重要性评估在优化中的作用。
|
5天前
|
机器学习/深度学习 算法 搜索推荐
R语言LASSO特征选择、决策树CART算法和CHAID算法电商网站购物行为预测分析
R语言LASSO特征选择、决策树CART算法和CHAID算法电商网站购物行为预测分析