搜索专项---最短路模型


文章目录

  • 迷宫问题
  • 武士风度的牛
  • 抓住那头牛

一、迷宫问题OJ链接

        本题思路:只需要记录各个点是有哪个点走过来的,就能递推得出路径。记录前驱假设从 1,1 这个点向下走到了2, 1,则将2,1这个点的前驱记为1,1。这样,将整张地图 bfs 后,各个点的前驱就被记录了下来。输出路径:经过 bfs ,各个点的前驱已经被记录下来,我们只需要从终点开始,依次找当前节点的前驱,就能一直找到起点,从而得到一条路径。当然,这条路径是终点到起点的路径,倒序输出即为起点到终点的路径。如果 bfs 是从终点开始,则讲过上述步骤,得到的就是从起点到终点的路径,不用倒序输出。

#include <bits/stdc++.h>#define x first
#define y secondtypedef std::pair<int,int> PII;constexpr int N=1010;int n;
int g[N][N];
bool st[N][N];
PII pre[N][N];//储存当前位置的前驱位置
std::queue<PII> q;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};void bfs(int ax,int ay)
{q.push({ax,ay});st[ax][ay]=true;while(!q.empty()){PII t=q.front();q.pop();for(int i=0;i<4;i++){int a=t.x+dx[i],b=t.y+dy[i];if(a<0||a>=n||b<0||b>=n) continue;if(g[a][b]) continue;if(!st[a][b]){q.push({a,b});pre[a][b]=t;st[a][b]=true;}}}}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)std::cin>>g[i][j];bfs(n-1,n-1);//从终点位置进行遍历PII end(0,0);while (true){std::cout<<end.x<<" "<<end.y<<std::endl;if (end.x == n - 1 && end.y == n - 1) break;end = pre[end.x][end.y];}
}

二、武士风度的牛OJ链接

   本题题解: 从牛的起点,进行 bfs 即可。根据题意,牛走的是日字, 八个点。因此,dx, dy 和之前的四个点是不同的。可以得出:dx = [-2, -1, 1, 2, 2, 1, -1, -2],dy = [1, 2, 2, 1, -1, -2, -2, -1]
具体的:找到牛的起点,从起点开始进行 bfs向八个方向进行探索,判断这八个点是否合法:不越界和牛能走。对于合法的点,记录从起点走过来的距离,也就是上个点的距离+1。将合法的点放入队列。如果在 bfs过程中遇到了终点(干草) ,则返回答案。

#include <bits/stdc++.h>#define x first
#define y secondtypedef std::pair<int,int> PII;constexpr int N=2000;int n,m;
char g[N][N];
int dist[N][N];
std::queue<PII> q;int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};int bfs(int ax,int ay)
{memset(dist,-1,sizeof dist);dist[ax][ay]=0;q.push({ax,ay});while(!q.empty()){PII t=q.front();q.pop();for(int i=0;i<8;i++){int a=t.x+dx[i],b=t.y+dy[i];if(a<0||a>=n||b<0||b>=m) continue;if(g[a][b]=='*') continue;if(dist[a][b]!=-1) continue;if(g[a][b]=='H') return dist[t.x][t.y]+1;dist[a][b]=dist[t.x][t.y]+1;q.push({a,b});}}}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cin>>m>>n;for(int i=0;i<n;i++) std::cin>>g[i];int ax,ay;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='K'){ax=i;ay=j;}std::cout<<bfs(ax,ay)<<std::endl;return 0;
}

三、抓住那头牛OJ链接

       本题思路: 这道题是一个一维的找最短路径的问题,无论+1,-1,* 2 花费都是1分钟,即权值相同, 所以才能用BFS去找最短路。假设当前点为t , 目标点为k出队扩展循环判断 1、如果t-1小于0了,那就不能走-1的方法 2、如果t+1 大于了N(10的5次方+10 ),就不能走+1的方法。 3、如果t * 2大于了N,也就不能走* 2的方法了。当然三个判断都应该加上此点是否被走过的条件,如果满足条件,就把其入队,出队时判断t是否等于k,如果相等就return距离。那么为什么N要取的比K大一点呢,因为先减1再乘2扩大会比先乘再减一缩小更快的接近K,1、当k为偶数,假设为100,当前点为51,那么减一再乘更快,2、当k为奇数,假设为99,当前点为50,那么先乘再减一时更快一点的。所以N要取的比K大一点,当超过N的时候就不会有这样的区别,一定是先减再乘可以更快的接近K。

#include <bits/stdc++.h>constexpr int N=1e5+10;int n,k;
int dist[N];
std::queue<int> q;int bfs()
{q.push(n);dist[n]=0;while(!q.empty()){auto t=q.front();q.pop();if(t==k) return dist[k];if(t-1>=0&&dist[t-1]==-1){q.push(t-1);dist[t-1]=dist[t]+1;}if(t+1<=N&&dist[t+1]==-1){q.push(t+1);dist[t+1]=dist[t]+1;}if(t*2<=N&&dist[t*2]==-1){q.push(t*2);dist[t*2]=dist[t]+1;}}
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);memset(dist,-1,sizeof dist);std::cin>>n>>k;std::cout<<bfs()<<std::endl;return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

C++进阶(十五)C++的类型转换

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、C语言中的类型转换二、为什么C需要四种类型转换三、C强制类型转换1、static_cast2、reint…

【必看】Onlyfans如何使用搜索功能?Onlyfans如何搜索博主?如何在OnlyFans搜索HongkongDoll

1. 什么是Onlyfans OnlyFans是一种内容订阅服务平台&#xff0c;它成立于2016年。 它允许内容创作者在平台上面分享自己的创作&#xff0c;如图片、视频等等&#xff0c;用户需要支付订阅费用才能查看创作者的内容。此外&#xff0c;用户还可以通过打赏的方式来让创作者为自己…

[Python进阶] 制作动态二维码

11.1 制作动态二维码 二维码&#xff08;QR code&#xff09;是一种二维条形码&#xff08;bar code&#xff09;&#xff0c;它的起源可以追溯到20世纪90年代初。当时&#xff0c;日本的汽车工业开始使用一种被称为QR码的二维条码来追踪汽车零部件的信息。 QR码是Quick Respo…

代码随想录算法训练营Day55|392.判断子序列、115.不同的子序列

目录 392.判断子序列 思路 ​算法实现 115.不同的子序列 思路 算法实现 总结 392.判断子序列 题目链接 文章链接 思路 利用动规五部曲进行分析&#xff1a; 1.确定dp数组及其下标含义&#xff1a; dp[i][j] 表示以下标i-1为结尾的字符串s&#xff0c;和以下标j-1为结尾的…

controlnet的模型下载

controlnet模型有sd15和基于sd15上的fp16版本 fp16版本的模型比较小&#xff0c;但功能效果跟sd15是一样的 controlnet的fp16模型下载地址 https://huggingface.co/comfyanonymous/ControlNet-v1-1_fp16_safetensors/tree/main controlnet的openpose里&#xff0c;有个dw_open…

寒假作业

手写盗版微信登入界面 #include "mainwindow.h" #include "ui_mainwindow.h"MainWindow::MainWindow(QWidget *parent): QMainWindow(parent), ui(new Ui::MainWindow) {ui->setupUi(this);this->resize(421,575);this->setFixedSize(421,575);th…

AI:126-基于深度学习的人体情绪识别与分析

🚀点击这里跳转到本专栏,可查阅专栏顶置最新的指南宝典~ 🎉🎊🎉 你的技术旅程将在这里启航! 从基础到实践,深入学习。无论你是初学者还是经验丰富的老手,对于本专栏案例和项目实践都有参考学习意义。 ✨✨✨ 每一个案例都附带有在本地跑过的关键代码,详细讲解供…

docker常用容器命令

首先说下容器&#xff1a; 它是指当docker运行镜像时&#xff0c;创建了一个隔离环境&#xff0c;称之为 容器。 这种方式优点&#xff1a;可以开启多个服务&#xff0c;服务之前是互相隔离的&#xff08;比如&#xff1a;在一台服务器上可以开启多个mysql&#xff0c;可以是…

2.12 分支、循环练习

1、选择题 1.1、以下程序的输出结果是 A 。 main() { int k11,k22,k33,x15; if(!k1) x--; else if(k2) if(k3) x4; else x3; printf(“x%d\n”,x); } A x4 B x15 C x14 D x3 解析&#xff1a;if(!k1) x--; 检查 k1 是否为0。因为 k1 的值为1&#xff0c;所…

论文阅读-One for All : 动态多租户边缘云平台的统一工作负载预测

论文名称&#xff1a;One for All: Unified Workload Prediction for Dynamic Multi-tenant Edge Cloud Platforms 摘要 多租户边缘云平台中的工作负载预测对于高效的应用部署和资源供给至关重要。然而&#xff0c;在多租户边缘云平台中&#xff0c;异构的应用模式、可变的基…

Netty Review - NioEventLoopGroup源码解析

文章目录 概述类继承关系源码分析小结 概述 EventLoopGroup bossGroup new NioEventLoopGroup(1); EventLoopGroup workerGroup new NioEventLoopGroup();这段代码是在使用Netty框架时常见的用法&#xff0c;用于创建两个不同的EventLoopGroup实例&#xff0c;一个用于处理连…

pycharm控制STM32F103ZET6拍照并上位机接收显示(OV7670、照相机、STM32、TFTLCD)

基于STM32的照相机 准备工作最终效果一、下位机1、主函数2、OV7670初始化 二、上位机1、控制拍照2、接收图片数据 三、资源获取 准备工作 一、硬件及片上资源: 1,串口1(波特率:921600,PA9/PA10通过usb转ttl连接电脑&#xff0c;或者其他方法)上传图片数据至上位机 2,串口2(波特…

文件包含知识点详细总结

如果想看图片和观感更好的话,可以直接去我的github或者gitbook github:https://github.com/kakaandhanhan/cybersecurity_knowledge_book-gitbook.22kaka.fun gitbook:http://22kaka.fun description: 这里将通过参考文章和做题一起进行总结,并且文件包含漏洞,很多都利用了…

【JavaEE】_CSS常用属性

目录 1. 字体属性 1.1 设置字体家族 font-family 1.2 设置字体大小 font-size 1.3 设置字体粗细 font-weight 1.4 设置字体倾斜 font-style 2. 文本属性 2.1 设置文本颜色 color 2.2 文本对齐 text-align 2.3 文本装饰 text-decoration 2.4 文本缩进 text-indent 2.…

PHP特性知识点总结

如果想观感更好看到图片,可以去我的gitbook或者github去看 github:https://github.com/kakaandhanhan/cybersecurity_knowledge_book-gitbook.22kaka.fun gitbook:http://22kaka.fun description: 专门出的关于php的特性比较,后面好像也有java的特性。 🏀 PHP特性知识点…

【hcie-cloud】【26】华为云Stack主机安全防护

文章目录 前言主机安全概述主机安全概念主机安全风险与挑战 - 黑客入侵安全风险管理难安全合规审查严格 主机安全服务HSS详述企业主机安全服务介绍主机安全服务 - 实现原理&#xff08;主机安全&#xff09;主机安全服务 - 实现原理&#xff08;容器安全&#xff09;主机安全服…

安装faiss环境教程

文章目录 打开环境安装faiss环境检查已安装的环境切换环境至faiss 打开环境 source activate # 打开环境安装faiss环境 conda create -n faiss_env # 安装faiss环境检查已安装的环境 conda info --envs # 检查已安装的环境切换环境至faiss conda a…

【JAVA-Day74】探讨Java字节输入流(InputStream)

标题 《深入探讨Java字节输入流(InputStream)的奥秘》摘要引言一、什么是字节输入流 &#x1f60a;扩展理解和代码示例工作原理示例代码注意事项 二、字节输入流操作 TXT &#x1f4c4;1. 打开文件2. 读取文件内容3. 关闭文件示例代码注意事项 三、字节输入流的应用场景 &#…

【ES】--Elasticsearch的分词器详解

目录 一、前言二、分词器原理1、常用分词器2、ik分词器模式3、指定索引的某个字段进行分词测试3.1、采用ts_match_analyzer进行分词3.2、采用standard_analyzer进行分词三、如何调整分词器1、已存在的索引调整分词器2、特别的词语不能被拆开一、前言 最近项目需求,针对客户提…