BFS算法——层层推进，最短之路，广度优先搜索算法的诗意旅程（下）

文章目录

  • 引言
  • 一. 迷宫中离入口最近的出口
    • 1.1 题目链接：https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/
    • 1.2 题目分析：
    • 1.3 思路讲解：
    • 1.4 代码实现:
  • 二. 最小基因变化
    • 2.1 题目链接：https://leetcode.cn/problems/minimum-genetic-mutation/description/
    • 2.2 题目分析：
    • 2.3 思路讲解：
    • 2.4 代码实现：
  • 三. 单词接龙
    • 3.1 题目链接：https://leetcode.cn/problems/word-ladder/description/
    • 3.2 题目分析：
    • 3.3 思路讲解：
    • 3.4 代码实现：
  • 四. 为高尔夫比赛砍树
    • 4.1 题目链接：https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/
    • 4.2 题目分析：
    • 4.3 思路讲解：
    • 4.4 代码实现：
  • 小结

在这里插入图片描述

引言

上篇我们介绍了BFS算法求取最短路径的代码实现，本篇将结合具体题目，进一步深化对于该方法的理解运用。

一. 迷宫中离入口最近的出口

1.1 题目链接：https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/

1.2 题目分析：

  • 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。
  • 同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
  • 可以上下左右在空格子内进行移动，无法穿过墙，要求寻找距离入口最近的出口
  • 每移动一次视为移动一步，求出最短步数

1.3 思路讲解：

利用层序遍历的思想，一层则可视为一步，其余步骤与上题基本相同。
注意处理边界情况！！！

1.4 代码实现:

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int step=0;
    bool vis[101][101]={false};//标记数组
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m=maze.size(),n=maze[0].size();
        queue<pair<int,int>> q;
        q.push({entrance[0],entrance[1]});//起点入队列
        vis[entrance[0]][entrance[1]]=true;
        while(q.size())
        {
            step++;
            int sz=q.size();
            for(int i=0;i<sz;i++)
            {
                auto [a,b]=q.front();
                q.pop();
                vis[a][b]=true;
                //下一层入队列
                for(int j=0;j<4;j++)
                {
                    int x=a+dx[j],y=b+dy[j];

                    //判断是否可以前进
                    if(x>=0 && x<m && y>=0 && y<n && maze[x][y]=='.' && vis[x][y]==false)
                    {
                        //判断是否为出口
                        if(x==0 || x==m-1 || y==0 || y==n-1)
                        {
                            return step;
                        }
                        q.push({x,y});
                        vis[x][y]=true;
                    }
                }
            }
        }
        return -1;

        
    }
};

二. 最小基因变化

2.1 题目链接：https://leetcode.cn/problems/minimum-genetic-mutation/description/

2.2 题目分析：

  • 一个基因序列由8个字符构成，字符只能为A，C，G，T
  • 给出start和end序列，以及基因库bank，每次可以对start内的一个字符进行A，C，G，T的变化
  • 每次变化后的序列都要在bank中，求取最少变化次数
  • 若无法变化成功，则返回-1

2.3 思路讲解：

首先考虑特殊情况：

  • 如果start==end，说明无须变化，直接返回次数0
  • 如果end不在bank内，说明不可能变化成功，直接返回-1

由于每次变化只能在ACGT的范围内，因此我们可以先定义一个string change=ACGT，类比之前变化时的数组dx和dy

  • 根据之前讲解的BFS思想，我们考虑创建一个标记数组vis，以及hash来判断变化后的字符串temp是否处于bank内。
  • 之后创建一个队列，将start序列入队列，根据层序遍历，每次对其进行ACGT的变化，因此一层就相当于变化一次，记录变化次数ret
  • 如果变化后的序列与end相等且在bank内，则说明变化成功，直接返回ret
  • 如果不相等且temp处于bank内，则将变化后的序列及录入vis内，避免重复判断

2.4 代码实现：

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> vis;//标记数组
        unordered_set<string> hash(bank.begin(),bank.end());
        //处理特殊情况
        if(startGene==endGene) return 0;
        if(!hash.count(endGene)) return -1;
        string change="ACGT";//每次的变化序列
        queue<string> q;
        q.push(startGene);
        vis.insert(startGene);
        int ret=0;//变化次数
        while(q.size())
        {
            ret++;//每层次数加1
            int sz=q.size();
            while(sz--)
            {
                string t=q.front();
                q.pop();
                for(int i=0;i<8;i++)
                {
                     string temp=t;//避免污染源字符串
                for(int j=0;j<4;j++)
                {
                   
                    temp[i]=change[j];
                    if(temp==endGene && hash.count(endGene))
                    {
                        return ret;
                    }//成功情况
                    if(temp!=endGene && hash.count(temp) && !vis.count(temp))
                    {
                        vis.insert(temp);
                        q.push(temp);
                    }
                }
                }
            }

        }
        return -1;


        
    }
};

三. 单词接龙

3.1 题目链接：https://leetcode.cn/problems/word-ladder/description/

3.2 题目分析：

本题与上题基因变化类似，都是给出start与end，每次变化一个字母，求最小变化次数

  • 每次变化一个字母后，字符串temp必须在给定的数组wordlist内
  • 如果无法成功变化为end，则返回0

3.3 思路讲解：

首先考虑特殊情况：

  • 如果end不在wordlist内，无论如何也无法成功变化，因此直接返回0

剩余思路与上题完全一致，只需要将遍历方向改为26个字符a->z即可。

注意本题要返回的是长度，start也算一个字符串，因此要在最小变化次数的基础上再加1

3.4 代码实现：

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> vis;//标记数组
        unordered_set<string> hash(wordList.begin(),wordList.end());
        //处理特殊情况
        if(!hash.count(endWord))
        {
            return 0;
        }
        int ret=1;//返回长度
        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);
        while(q.size())
        {
            ret++;//每层长度+1
            int sz=q.size();
            while(sz--)
            {
                string t=q.front();
                q.pop();
                int m=t.size();//该单词长度
                for(int i=0;i<m;i++)
                {
                    
                    for(char ch='a';ch<='z';ch++)
                    {
                       string temp=t;//避免污染源字符串
                        temp[i]=ch;
                        if(temp==endWord)
                        {
                            return ret;
                        }//成功情况
                        if(temp!=endWord && hash.count(temp) && !vis.count(temp))
                        {
                            vis.insert(temp);
                            q.push(temp);
                        }
                    }
                }
            }
        }
        return 0;
        
    }
};

四. 为高尔夫比赛砍树

4.1 题目链接：https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/

4.2 题目分析：

给定一个m*n的矩阵，其中

  • 0表示障碍，无法行走
  • 1表示地面，可以通行
  • 大于1的数表示该处存在一棵树，且值的大小为树的高度，可以通行

要求从(0,0)开始，按照树的高度从低到高砍完所有树,且每次砍树之后，该处变为1

返回砍完所有树所需的最小步数

如果无法砍完所有树，则返回-1

4.3 思路讲解：

首先我们需要明确，只有遇到0时，才无法通行

  • m*n的矩阵可以类比之前的迷宫问题，定义dx和dy数组，进行方向上的移动
  • 遍历矩阵，按照树的高度由低到高用数组trees存储树节点

由于题目要求从低到高进行砍树，因此本题就转化为遍历trees，求两两相邻节点的最小步数之和。

求取两个点的最短路径，bfs遍历即可。

4.4 代码实现：

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int m,n;//数组规模
    int ret=0;//最终步数
    bool vis[51][51];//标记数组
    int bfs(vector<vector<int>>& forest,int bx,int by,int ex,int ey)
    {
        queue<pair<int,int>> q;
        int step=0;//步数
        memset(vis,0,sizeof(vis));//重置清零操作
        //处理特殊情况
        if(bx==ex && by==ey)
        {
            return 0;
        }
        q.push({bx,by});//起点入队列
        vis[bx][by]=true;//更新标记
        while(q.size())
        {
            int sz=q.size();
            step++;
            while(sz--)
            {
                auto [a,b]=q.front();
                q.pop();
                for(int i=0;i<4;i++)
                {
                    int x=a+dx[i],y=b+dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false &&forest[x][y])
                    {
                    if (x == ex && y == ey)
                    {
                        return step;
                    }//成功情况
                    q.push({x,y});
                    vis[x][y]=true;
                    }

                }
            }
        }
        return -1;//未成功找到

    }
    int cutOffTree(vector<vector<int>>& forest) {
        m=forest.size(),n=forest[0].size();
        vector<pair<int,int>> trees;
        //存储树节点
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(forest[i][j]>1)
                {
                    trees.push_back({i,j});
                }
            }
        }
        //排序
        sort(trees.begin(),trees.end(),[&](const pair<int,int>& a,const pair<int,int>& b)
        {
            return forest[a.first][a.second]<forest[b.first][b.second];
        });
        int bx=0,by=0;//起点
        for(auto& [a,b] :trees)
        {
            int temp=bfs(forest,bx,by,a,b);
            if(temp==-1)
            {
                return -1;
            }//无法砍完所有的树
            ret+=temp;//累加
            bx=a,by=b;//更新起点
        }
        return ret;

        
    }
};

小结

本篇关于bfs算法求取最短路径的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/972937.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux----Makefile基础

Linux----Makefile基础

Makefile 是自动化构建工具 make 的配置文件&#xff0c;用于定义编译规则和依赖关系&#xff0c;实现高效增量编译。 初识makefile 1. 什么是 make&#xff1f; 定义&#xff1a; make 是一个命令行工具&#xff08;可执行程序&#xff09;&#xff0c;用于解析并执行 Makef…
阅读更多...
leetcode876.链表的中间结点

leetcode876.链表的中间结点

目录 问题描述示例提示 具体思路思路一 代码实现 问题描述 给你单链表的头结点 head &#xff0c;请你找出并返回链表的中间结点。 如果有两个中间结点&#xff0c;则返回第二个中间结点。 题目链接&#xff1a;链表的中间结点 示例 提示 链表的结点数范围是 [1, 100]   1 &…
阅读更多...
设计变更滞后导致生产计划混乱？PLM与MES集成实时同步

设计变更滞后导致生产计划混乱？PLM与MES集成实时同步

当产品设计在PLM系统中发生变更时&#xff0c;这些变更信息却无法及时、准确地传递到MES系统中。结果是&#xff0c;车间生产现场仍然按照旧的设计指令执行&#xff0c;导致生产出的产品与设计要求不符&#xff0c;不仅引发质量问题&#xff0c;还可能造成停工、物料浪费甚至客…
阅读更多...
20250220解决使用top指令查看荣品PRO-RK3566开发板的CPU占用率为400%的问题

20250220解决使用top指令查看荣品PRO-RK3566开发板的CPU占用率为400%的问题

20250220解决使用top指令查看荣品PRO-RK3566开发板的CPU占用率为400%的问题 2025/2/20 19:14 缘起&#xff0c;使用荣品PRO-RK3566开发板配套的百度网盘中的SDK&#xff1a;Android13编译之后&#xff0c;查看RK3566的CPU占用率为400%。 开机就是400%&#xff0c;什么时候都是4…
阅读更多...
巧用GitHub的CICD功能免费打包部署前端Node项目

巧用GitHub的CICD功能免费打包部署前端Node项目

近年来&#xff0c;随着前端技术的发展&#xff0c;前端项目的构建和打包过程变得越来越复杂&#xff0c;占用的资源也越来越多。我有一台云服务器&#xff0c;原本打算使用Docker进行部署&#xff0c;以简化操作流程。然而&#xff0c;只要执行sudo docker-compose -f deploy/…
阅读更多...
web 通识3

web 通识3

目录 6 通向3.0区块链技术前沿发展 7.主流区块链项目介绍 9.区块链行业应用总览 6 通向3.0区块链技术前沿发展 隔离见证&#xff1a;将一部分信息放在别的地方&#xff0c;这样原本的地方就可以容纳更多的东西 隔离见证和树图都是通过扩大容量来提高性能 闪电网络&#xf…
阅读更多...
Hadoop一 HDFS分布式文件系统

Hadoop一 HDFS分布式文件系统

一 分布式文件存储 了解为什么海量数据需要使用分布式存储技术 100T数据太大&#xff0c;单台服务器无法承担。于是&#xff1a; 分布式服务器集群 靠数量取胜&#xff0c;多台服务器组合&#xff0c;才能Hold住&#xff0c;如下 分布式不仅仅是解决了能存的问题&#xff…
阅读更多...
java练习（33）

java练习（33）

ps:题目来自力扣 最强回文子串 给你一个字符串 s&#xff0c;找到 s 中最长的 回文 子串。 class Solution {public String longestPalindrome(String s) {if (s null || s.length() < 1) {return "";}int start 0, end 0;for (int i 0; i < s.length();…
阅读更多...
分布式大语言模型服务引擎vLLM论文解读

分布式大语言模型服务引擎vLLM论文解读

论文地址&#xff1a;Efficient Memory Management for Large Language Model Serving with PagedAttention 摘要 大语言模型&#xff08;LLMs&#xff09;的高吞吐量服务需要一次对足够多的请求进行批处理。然而&#xff0c;现有系统面临困境&#xff0c;因为每个请求的键值…
阅读更多...
日期类（完全讲解版）

日期类（完全讲解版）

1. 类的设计思想 Date 类的设计目的是为了封装和处理日期信息&#xff0c;它提供了对日期的基本操作&#xff0c;如日期加减、日期比较、日期合法性检查等。类中的私有成员 int _year, int _month, int _day 存储了日期的年、月、日。 类的声明和构造 Date 类的声明&#xff1…
阅读更多...
微信小程序（uni）+蓝牙连接+Xprint打印机实现打印功能

微信小程序（uni）+蓝牙连接+Xprint打印机实现打印功能

1.蓝牙列表实现&#xff0c;蓝牙设备展示&#xff0c;蓝牙连接 <template><view class"container"><view class"container_top"><view class"l">设备名称</view><view class"r">{{state.phoneNam…
阅读更多...
zookeeper集群配置

zookeeper集群配置

配置 一、配置myid文件 # 进入解压好的文件夹下面 touch myid vim myid # master节点写0&#xff0c;slave1节点写1&#xff0c;slave2节点写2二、配置zoo.cfg文件 1.在master节点编辑zookeeper配置文件 # 进入解压好的文件夹下面 cd conf/ cp zoo_sample.cfg zoo.cfg vim …
阅读更多...
C++ Primer 类的静态成员

C++ Primer 类的静态成员

欢迎阅读我的 【CPrimer】专栏 专栏简介&#xff1a;本专栏主要面向C初学者&#xff0c;解释C的一些基本概念和基础语言特性&#xff0c;涉及C标准库的用法&#xff0c;面向对象特性&#xff0c;泛型特性高级用法。通过使用标准库中定义的抽象设施&#xff0c;使你更加适应高级…
阅读更多...
Ubuntu 服务器Llama Factory 搭建DeepSeek-R1微调训练环境

Ubuntu 服务器Llama Factory 搭建DeepSeek-R1微调训练环境

1.首先了解一下什么是LLM微调 LLM 微调指的是在已经预训练好的大型语言模型基础上&#xff0c;使用特定的任务数据或领域数据&#xff0c;通过进一步的训练来调整模型的参数&#xff0c;使其在特定任务或领域上能够表现得更好。简单来说&#xff0c;就是对一个已经具备了丰富语…
阅读更多...
C++17 中的 std::to_chars 和 std::from_chars：高效且安全的字符串转换工具

C++17 中的 std::to_chars 和 std::from_chars：高效且安全的字符串转换工具

文章目录 1. 传统转换方法的局限性2. std::to_chars&#xff1a;数值到字符串的高效转换函数原型&#xff1a;返回值&#xff1a;示例代码&#xff1a;输出&#xff1a; 3. std::from_chars&#xff1a;字符串到数值的高效解析函数原型&#xff1a;返回值&#xff1a;示例代码&…
阅读更多...
【Alertmanager】alertmanager告警系统原理剖析与应用实战，应有尽有非常全面

【Alertmanager】alertmanager告警系统原理剖析与应用实战，应有尽有非常全面

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全…
阅读更多...
VScode 使用Deepseek又方便又好用的另一款插件

VScode 使用Deepseek又方便又好用的另一款插件

一、Continue continue类似于copilot&#xff0c;包含5大核心功能&#xff1a;AI对话编程、代码自动补全、代码智能编辑、上下文提供器、快捷键操作&#xff0c;能满足编程的大部分需求。 在AI大模型的支持上&#xff0c;continue能连接包括DeepSeek、OpenAI、Claude在内的十…
阅读更多...
互联网 Java 工程师面试题（Java 面试题五）

互联网 Java 工程师面试题（Java 面试题五）

JVM 底层 与 GC&#xff08;Garbage Collection&#xff09; 的面试问题 31、64 位 JVM 中&#xff0c;int 的长度是多数&#xff1f; Java 中&#xff0c;int 类型变量的长度是一个固定值&#xff0c;与平台无关&#xff0c;都是 32 位。意思就 是说&#xff0c;在 32 位 和 6…
阅读更多...
【设计模式精讲】创建型模式之工厂方法模式（简单工厂、工厂方法）

【设计模式精讲】创建型模式之工厂方法模式（简单工厂、工厂方法）

文章目录 第四章 创建型模式4.2 工厂方法模式4.2.1 需求: 模拟发放奖品业务4.2.2 原始开发方式4.2.3 简单工厂模式4.2.3.1 简单工厂模式介绍4.2.3.2 简单工厂原理4.2.3.3 简单工厂模式重构代码4.2.3.4 简单工厂模式总结 4.2.4 工厂方法模式4.2.4.1 工厂方法模式介绍4.2.4.2 工厂…
阅读更多...
pytorch cnn 实现猫狗分类

pytorch cnn 实现猫狗分类

文章目录 [toc] 1. 导入必要的库2. 定义数据集类3. 数据预处理和加载4. 定义 CNN 模型5. 定义损失函数和优化器6. 训练模型7. 保存模型8. 使用模型进行预测9 完整代码10. 总结 1. 导入必要的库 import torch import torch.nn as nn import torch.optim as optim from torch.ut…
阅读更多...
最新文章

Copyright @ 2022~2023