Offer必备算法26_BFS解决最短路_四道力扣题(由易到难)

目录

①力扣1926. 迷宫中离入口最近的出口

解析代码

②力扣433. 最小基因变化

解析代码

③力扣127. 单词接龙

解析代码

④力扣675. 为高尔夫比赛砍树

解析代码

本篇完。


①力扣1926. 迷宫中离入口最近的出口

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

难度 中等

给你一个 m x n 的迷宫矩阵 maze (下标从 0 开始),矩阵中有空格子(用 '.' 表示)和墙(用 '+' 表示)。同时给你迷宫的入口 entrance ,用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作,你可以往  或者  移动一个格子。你不能进入墙所在的格子,你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子entrance 格子 不算 出口。

请你返回从 entrance 到最近出口的最短路径的 步数 ,如果不存在这样的路径,请你返回 -1 。

示例 1:

输入:maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
输出:1
解释:总共有 3 个出口,分别位于 (1,0),(0,2) 和 (2,3) 。
一开始,你在入口格子 (1,2) 处。
- 你可以往左移动 2 步到达 (1,0) 。
- 你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以,最近的出口是 (0,2) ,距离为 1 步。

示例 2:

输入:maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
输出:2
解释:迷宫中只有 1 个出口,在 (1,2) 处。
(1,0) 不算出口,因为它是入口格子。
初始时,你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以,最近的出口为 (1,2) ,距离为 2 步。

示例 3:

输入:maze = [[".","+"]], entrance = [0,0]
输出:-1
解释:这个迷宫中没有出口。

提示:

  • maze.length == m
  • maze[i].length == n
  • 1 <= m, n <= 100
  • maze[i][j] 要么是 '.' ,要么是 '+' 。
  • entrance.length == 2
  • 0 <= entrancerow < m
  • 0 <= entrancecol < n
  • entrance 一定是空格子。
class Solution {
public:int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {}
};

解析代码

        利用层序遍历来解决迷宫问题,是最经典的做法。我们可以从起点开始层序遍历,并且在遍历的过程中记录当前遍历的层数。这样就能在找到出口的时候,得到起点到出口的最短距离。

class Solution {int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};
public:int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int m = maze.size(), n = maze[0].size(), ret = 0;vector<vector<bool>> vis(m, vector<bool>(n, false)); // 下标是否被访问过queue<vector<int>> q; // 存下标的队列q.push(entrance);   // 入口入队vis[entrance[0]][entrance[1]] = true;while(!q.empty()){++ret; // 一层加一次步数int size = q.size();for(int i = 0; i < size; ++i) // 访问当前层{vector<int> tmp = q.front();q.pop();for(int j = 0; j < 4; ++j){int x = tmp[0] + dx[j], y = tmp[1] + dy[j];if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && !vis[x][y]){if(x == 0 || x == m - 1 || y == 0 || y == n - 1)return ret; // 是出口就返回q.push({x, y});vis[x][y] = true;}}}}return -1;}
};


②力扣433. 最小基因变化

433. 最小基因变化

难度 中等

基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是 'A''C''G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

  • 例如,"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化,只有基因库中的基因才是有效的基因序列。(变化后的基因必须位于基因库 bank 中)

给你两个基因序列 start 和 end ,以及一个基因库 bank ,请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化,返回 -1 。

注意:起始基因序列 start 默认是有效的,但是它并不一定会出现在基因库中。

示例 1:

输入:start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出:1

示例 2:

输入:start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出:2

示例 3:

输入:start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出:3

提示:

  • start.length == 8
  • end.length == 8
  • 0 <= bank.length <= 10
  • bank[i].length == 8
  • startend 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成
class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {}
};

解析代码

        如果将每次字符串的变换抽象成图中的两个顶点和一条边的话,问题就变成了边权为 1 的最短路问题。 因此,从起始的字符串开始,来一次 bfs 即可。

class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_set<string> bankHash(bank.begin(), bank.end());unordered_set<string> vis;string chargeArr = "ACGT";if(startGene == endGene)return 0;if(!bankHash.count(endGene))return -1;int ret = 0;queue<string> q;q.push(startGene);vis.insert(startGene);while(!q.empty()){++ret;int size = q.size();for(int i = 0; i < size; ++i){string t = q.front();q.pop();for(int j = 0; j < 8; ++j){for(int k = 0; k < 4; ++k){string tmp = t;tmp[j] = chargeArr[k];if(bankHash.count(tmp) && !vis.count(tmp)) // 有效的且没访问过{if(tmp == endGene)return ret;q.push(tmp);vis.insert(tmp);}}}}}return -1;}
};


③力扣127. 单词接龙

127. 单词接龙

难度 困难

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk

  • 每一对相邻的单词只差一个字母。
  •  对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。
  • sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ,返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0 。

示例 1:

输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出:5
解释:一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2:

输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出:0
解释:endWord "cog" 不在字典中,所以无法进行转换。

提示:

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWordendWord 和 wordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有字符串 互不相同
class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {}
};

解析代码

        和力扣433. 最小基因变化一样,如果将每次字符串的变换抽象成图中的两个顶点和一条边的话,问题就变成了边权为 1 的最短路问题。 因此,从起始的字符串开始,来一次 bfs 即可。

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> wordListHash(wordList.begin(), wordList.end());unordered_set<string> vis;if(!wordListHash.count(endWord))return 0;int ret = 1;queue<string> q;q.push(beginWord);vis.insert(beginWord);while(!q.empty()){++ret;int size = q.size();while(size--){string t = q.front();q.pop();for(int i = 0; i < t.size(); ++i){for(char ch = 'a'; ch <= 'z'; ++ch){string tmp = t;tmp[i] = ch;if(wordListHash.count(tmp) && !vis.count(tmp)){if(tmp == endWord)return ret;q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};


④力扣675. 为高尔夫比赛砍树

675. 为高尔夫比赛砍树

难度 困难

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 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) 位置的树,可以直接砍去,不用算步数。

提示:

  • m == forest.length
  • n == forest[i].length
  • 1 <= m, n <= 50
  • 0 <= forest[i][j] <= 10^9
class Solution {
public:int cutOffTree(vector<vector<int>>& forest) {}
};

解析代码

        先找出砍树的顺序,然后按照砍树的顺序,一个一个地用 bfs 求出最短路即可。求最短路就是力扣1926. 迷宫中离入口最近的出口。

class Solution {int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};int m = 0, n = 0;bool vis[51][51];public:int cutOffTree(vector<vector<int>>& forest) {m = forest.size(), n = forest[0].size();map<int, pair<int,int>> hash; // 数组值和下标,按数组值排序for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(forest[i][j] > 1) // 0不可走,1是地面hash[forest[i][j]] = {i, j};}}int ret = 0;pair<int,int> start = make_pair(0, 0);for(auto& [e, end] : hash) // 取下标{int step = bfs(forest, start, end);if(step == -1)return -1;ret += step;start = end;}return ret;}int bfs(vector<vector<int>>& forest, pair<int,int> start, pair<int,int> end){if(start == end)return 0;memset(vis, 0, sizeof(vis)); // 清空之前的数据queue<pair<int, int>> q;q.push(start);auto [a, b] = q.front();vis[a][b] = true;int ret = 0;while(!q.empty()){++ret;int sz = q.size();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 && forest[x][y] && !vis[x][y]){if(x == end.first && y == end.second)return ret;q.push({x, y});vis[x][y] = true;}}}}return -1;}
};


本篇完。

下一篇动态规划类型的是完全背包类型的OJ。

下下篇是多源BFS类型的OJ。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【简明图文教程】Node.js的下载、安装、环境配置及测试

文章目录 前言下载Node.js安装Node.js配置Node.js配置环境变量测试后言 前言 本教程适用于小白第一次从零开始进行Node.js的下载、安装、环境配置及测试。 如果你之前已经安装过了Node.js或删除掉了Node.js想重新安装&#xff0c;需要先参考以下博客进行处理后&#xff0c;再根…

社交网络与Web3:数字社交的下一阶段

随着信息技术的飞速发展&#xff0c;人们的社交方式也发生了巨大的变化。从最初的互联网聊天室到如今的社交网络平台&#xff0c;我们已经见证了数字社交的不断演变和发展。而随着区块链技术的兴起&#xff0c;Web3时代的到来将为数字社交带来全新的可能性和挑战。本文将探讨社…

milvus各组件的结构体分析

milvus各组件的结构体分析 各组件启动&#xff0c;需要构建各组件的结构体&#xff0c;一共8个。 runComponent(ctx, localMsg, wg, components.NewRootCoord, metrics.RegisterRootCoord) runComponent(ctx, localMsg, wg, components.NewProxy, metrics.RegisterProxy) run…

游戏开发者必看:Perforce Helix Core 的功能特点及游戏开发中的常用工具、典型用例介绍

「不出海&#xff0c;即出局」随着全球化的加速发展&#xff0c;企业出海已成燎原之势。日前&#xff0c;2024 亚马逊云科技出海全球化论坛在深圳成功举办。龙智携手 Perforce 亮相游戏行业展区&#xff0c;展示了Perforce Helix Core如何与主流游戏开发引擎高效集成&#xff0…

Docker安装部署Jenkins并发布NetCore应用

Docker安装Jenkins # 拉取镜像 docker pull jenkins/jenkins # 查看镜像 docker images # 运行jenkins # 8080端口为jenkins Web 界面的默认端口 13152是映射到外部 &#xff1a;前面的是映射外部 # 50000端口为jenkins 的默认代理节点&#xff08;Agent&#xff09;通信端口…

FFmpeg: 自实现ijkplayer播放器--06封装打开和关闭stream

文章目录 流程图stream openstream close流程图 stream open 初始化SDL以允许⾳频输出;初始化帧Frame队列初始化包Packet队列初始化时钟Clock初始化音量创建解复用读取线程read_thread创建视频刷新线程video_refresh_threadint FFPlayer::stream_open(const char

java:多线程解决生产者消费者问题

生产者消费者问题 生产者消费者问题&#xff0c;也称有限缓冲问题&#xff0c;是一个多线程同步问题的经典案例。该问题描述了共享固定大小缓冲区的两种线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中…

第十三届蓝桥杯省赛大学B组编程题(c++)

D.刷题统计 二分(AC): 注意:二分时右边界 right 的确定 #include<iostream> using namespace std; long long a,b,n; bool check(long long x){long long tx/7;x%7;long long temp0;if(x<5) tempx*a;else temp5*a(x-5)*b;long long cntt*(5*a2*b)temp;return cnt&g…

【网站项目】驾校报名小程序

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

【Linux学习笔记】安卓设置内核信息的打印级别

开发环境 开发板&#xff1a;正点原子RK3568开发板安卓版本&#xff1a;11 问题描述 在串口调试过程中经常打印出这样的一些信息 极影响调试&#xff0c;暂时又没什么用&#xff0c;有些时候还不能给它直接关了。尤其是这个信息 healthd: battery l50 v3 t2.6 h2 st3 fc10…

如何使用pytorch进行图像分类

如何使用pytorch进行图像分类https://featurize.cn/notebooks/5a36fa40-490e-4664-bf98-aa5ad7b2fc2f

Unity笔记之Android打包、减小包体之类的问题

打包问题 问题1&#xff1a; 一般大部分问题就是JDK、SDK、NDK之类的问题。现在是其他的问题&#xff0c;之前遇到过&#xff0c;好久没玩android了都忘了。 这试了半天&#xff0c;结果是需要有密钥库。那就给他创建一个填一下就行了 &#xff08;在网上看了半天&#xff…

weblogic oracle数据源配置

在weblogic console中配置jdbc oracle数据源 1. base_domain->Service->DataSources 在Summary of JDBC Data Sources中,点击New, 选择【Generic Data Source】通用数据源。 2. 设置数据源Name和JNDI name 注:设置的JNDI Name是Java AP中连接DB使用的数据源名 JND…

Vue ElementUI el-input-number 改变控制按钮 icon 箭头为三角形

el-input-number 属性 controls-position 值为 right 时&#xff1b; <el-input-number v-model"num" controls-position"right" :min"1" :max"10"></el-input-number>原生效果 修改后效果 CSS 修改 .el-input-number…

sql注入之延时注入

1.1 延时盲注原理 延时盲注&#xff0c;也称为时间盲注或延迟注入&#xff0c;是一种SQL盲注的手法。其原理在于利用执行时间差来判断是否执行成功。攻击者提交一个对执行时间敏感的SQL语句&#xff0c;通过执行时间的长短来判断注入是否成功。如果注入成功&#xff0c;执行时…

2024年生物医学与食品安全国际会议 (ICBFS 2024)

2024年生物医学与食品安全国际会议 (ICBFS 2024) 2024 International Conference on Environmental Prevention and New Materials 【会议简介】 2024年生物医学与食品安全国际会议即将在成都召开。本次会议将汇聚全球生物医学与食品安全领域的专家学者&#xff0c;共同探讨生…

CSS导读 (元素显示模式 下)

&#xff08;大家好&#xff0c;今天我们将继续来学习CSS的相关知识&#xff0c;大家可以在评论区进行互动答疑哦~加油&#xff01;&#x1f495;&#xff09; 目录 3.6 元素显示模式转换 3.7 (一个小技巧)单行文字垂直居中的代码 3.8 单行文字垂直居中的原理 3.9 小案例…

学习笔记------约束的管理

此篇记录FPGA的静态时序分析&#xff0c;在学习FPGA的过程中&#xff0c;越发觉得对于时序约束只是懂了个皮毛。现在记录一下自己的学习过程。 本文摘自《VIVADO从此开始》高亚军 为什么要进行约束&#xff1f;约束的目的是什么&#xff1f; 简单来说&#xff0c;就是需要在…

提高APP安全性的必备加固手段——深度解析代码混淆技术

​ APP 加固方式 iOSAPP 加固是优化 APK 安全性的一种方法&#xff0c;常见的加固方式有混淆代码、加壳、数据加密、动态加载等。下面介绍一下 iOSAPP 加固的具体实现方式。 混淆代码&#xff1a; 使用 ProGuard 工具可以对代码进行混淆&#xff0c;使得反编译出来的代码很难…

数据结构复习指导之绪论(算法的概念以及效率的度量)

文章目录 绪论&#xff1a; 2.算法和算法评价 知识总览 2.1算法的基本概念 知识点回顾与重要考点 2.2算法效率的度量 知识总览 1.时间复杂度 2.空间复杂度 知识点回顾与重要考点 归纳总结 绪论&#xff1a; 2.算法和算法评价 知识总览 2.1算法的基本概念 算法( Al…