算法学习之BFS
关于BFS我的理解是根据离我们当前这个点的权重来移动，这里权重也可以理解为离这个点的距离，
从起点开始，往前走一步，记录下所有第一步能走到的点开始，然后从所有第一部能走到的点开始向前走第二步，重复下去，一直到终点，输出步数即可，
实现方式：广度优先搜索
这是一个例题：
下面是用队列写的方法
我之前疑惑的点是while(!q.empty())不知道什么时候停止，后来想了想，觉得如果广搜到最后一个位置的话，怎么判断，所以在代码中加了一个判断是否到达目标点的判断。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;typedef pair<int, int> PII; // 定义坐标对类型
const int N = 110; // 地图最大尺寸int g[N][N]; // 存储地图，0表示可通行，1表示障碍
int f[N][N]; // 存储每个点到起点的最短距离
int n, m; // 地图的行数和列数// 广度优先搜索函数，起点坐标为(a, b)
void bfs(int a, int b) {queue<PII> q;q.push({ a, b });f[a][b] = 0; // 起点距离为0while (!q.empty()) {PII current = q.front();q.pop();// 新增：判断当前节点是否是终点if (current.first == n && current.second == m) {cout << f[current.first][current.second];return; // 找到终点，直接结束函数}// 方向增量：上、右、下、左int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };for (int i = 0; i < 4; i++) {int x = current.first + dx[i];int y = current.second + dy[i];// 检查坐标合法性（注意地图是 1-based）if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == 0) {g[x][y] = 1; // 标记为已访问f[x][y] = f[current.first][current.second] + 1;q.push({ x, y });}}}// 队列清空仍未找到终点，说明无解cout << "No path!";
}
int main() {memset(g, 1, sizeof(g)); // 初始化地图周围为障碍（每个字节设为1，int实际值为0x01010101）cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> g[i][j]; // 读取地图数据（1-based）bfs(1, 1); // 从起点(1,1)开始BFSreturn 0;
}下面这个做法是模拟队列
#include<iostream>
#include<cstring>
using namespace std;typedef pair<int, int> PII;
const int N = 110;int g[N][N]; // 地图：0可通行，1障碍
int d[N][N]; // 到起点的距离，-1表示未访问
int n, m; // 实际行数n，列数m
PII q[N * N]; // 数组模拟队列int bfs() {int hh = 0, tt = 0;q[0] = {0, 0}; // 起点(0,0)入队memset(d, -1, sizeof(d));d[0][0] = 0; // 起点距离为0// 方向：上、下、左、右int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};while (hh <= tt) {auto t = q[hh++]; // 取出队头if (t.first == n-1 && t.second == m-1) {return d[t.first][t.second];}// 遍历四个方向for (int i = 0; i < 4; i++) {int x = t.first + dx[i], y = t.second + dy[i];// 合法性检查：不越界、可通行、未被访问if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {d[x][y] = d[t.first][t.second] + 1; // 更新距离q[++tt] = {x, y}; // 新坐标入队}}}return -1; // 队列清空仍未找到终点，返回-1
}int main() {cin >> n >> m;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) // 正确遍历列数mcin >> g[i][j];cout << bfs() << endl;return 0;
}相关文章：
算法学习之BFS
关于BFS我的理解是根据离我们当前这个点的权重来移动，这里权重也可以理解为离这个点的距离， 从起点开始，往前走一步，记录下所有第一步能走到的点开始，然后从所有第一部能走到的点开始向前走第二步，重复下去…...
每日小积累day1
网络： g是用来检测网络联通性的的诊断工具，使用的协议是ICMP 显示数据包括 ICMP数据：序列号，存活时间（TTL） 目标主机域名IP 往返时间（RTT） 统计数据（平均RTT等等&a…...
【NLP】13. NLP推理方法详解 --- 穷举和贪心搜索
NLP推理方法详解 — 穷举和贪心搜索 在自然语言处理（NLP）任务中，推理（Inference）是指在给定模型的情况下，找到最可能的输出序列。由于模型通常是神经网络，它会为每个可能的输出分配一个概率&am…...
基于 Python 深度学习 lstm 算法的电影评论情感分析可视化系统（2.0 系统全新升级，已获高分通过）
大家好，欢迎来到我的技术专栏！今天我将和大家聊聊如何利用 Python 的深度学习技术，打造一个集电影评论情感分析与可视化展示于一体的系统。这个系统不仅能自动采集和解析海量影评，还能实时生成直观的情感趋势图表，对于…...
妙用《甄嬛传》中的选妃来记忆概率论中的乘法公式
强烈推荐最近在看的不错的B站概率论课程 《概率统计》正课，零废话，超精讲！【孔祥仁】 《概率统计》正课，零废话，超精讲！【孔祥仁】_哔哩哔哩_bilibili 其中概率论中的乘法公式，老师用了《甄嬛传…...
linux--------------进程控制
1.进程创建 1.1fork函数初识 在linux中fork函数是⾮常重要的函数，它从已存在进程中创建⼀个新进程。新进程为⼦进程，⽽原进 程为⽗进程。 #include <unistd.h> pid_t fork(void); 返回值：⾃进程中返回0，⽗进程返回⼦进程id…...
Video Transformer Network
目录 摘要 Abstract VTN 背景 模型框架 视频特征提取 时空位置编码 Transformer编码器 任务特定头 关键创新 实验 代码 总结 摘要 Video Transformer Network 是基于Transformer架构改进的视频理解模型，旨在解决传统3D卷积神经网络在长距离依赖建模和…...
Java网络编程演进：从NIO到Netty的UDP实践全解析
前言 在当前高并发、大数据量的互联网环境下，高性能的网络通信框架变得越来越重要。本文将深入探讨Java网络编程的演进，从NIO到Netty，并通过实际案例分析Netty的优势和应用。（本次主要以UDP请求为例） Java网络编程演…...
Linux系统中快速安装docker
1 查看是否安装docker 要检查Ubuntu是否安装了Docker，可以使用以下几种方法： 方法1：使用 docker --version 命令 docker --version如果Docker已安装，输出会显示Docker的版本信息，例如： Docker version …...
人工智能之数学基础：幂法和反幂法求特征值和特征向量
本文重点 特征值和特征向量是矩阵的重要性质，我们前面学习了矩阵的正交分解，要想完成正交分解需要求出一个矩阵的特征值和特征向量。有的时候，我们只需要求出一个矩阵的最大的特征值以及矩阵的最小特征值，它们以及它们对应的特征向量具有特殊的含义，下面我们介绍两种方法…...
数据结构 -- 树的应用（哈夫曼树和并查集）
树的应用 哈夫曼树 带权路径长度 结点的权：有某种现实含义的数值（如：表示结点的重要性等） 结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积 树的带权路径…...
游戏引擎学习第193天
仓库:https://gitee.com/mrxiao_com/2d_game_4 回顾 我们昨天做了一些非常有趣的实验。在实验中，我们的目标是实现一个能够在运行时改变的编译时常量的概念。最开始，这个想法纯粹是出于一时的兴趣，觉得这应该是个很有意思的尝试。于是我们进…...
数据结构每日一题day7（顺序表）★★★★★
题目描述：从顺序表中删除其值在给定值s与t之间(包含s和 t，要求 s<t)的所有元素，若s或t不合理或顺序表为空，则返回 false，若执行成功则返回 true。 算法思想： 输入检查：若顺序表为空、指针为…...
ACM模式常用方法总结（Java篇）
文章目录 一、ACM输入输出模式二、重要语法2.1、导包2.2、读取数据2.3、判断是否有下一个数据2.4、输出2.5、关闭scanner2.6、易踩坑点 一、ACM输入输出模式 在力扣上编写代码时使用的是核心代码模式，如果在面试中遇到ACM模式就会比较迷茫？ACM模式要求你…...
SpringCould微服务架构之Docker（6）
容器的基本命令： 1. docker exec ：进入容器执行命令 2. docker logs: -f 持续查看容器的运行日志 3. docker ps：查看所有运行的容器和状态 案例：创建运行一个容Nginx容器 docker run--name myNginx -p 80:80 -d nginx 命…...
脑疾病分类的疑惑【7】一般FMRI数据都存储为什么格式？能不能给我用数据简单的描述一下FMRI是如何存储的？
fMRI 数据通常以 NIfTI（Neuroimaging Informatics Technology Initiative） 格式存储，这是一种专为神经影像设计的开放标准格式。以下是简化说明和示例： 1. 常见fMRI数据格式 格式扩展名特点NIfTI.nii 或 .nii.gz最常用࿰…...
DOM 加载函数
DOM 加载函数 在Web开发中，DOM（文档对象模型）加载函数是一个核心概念。它指的是在页面加载过程中，浏览器如何处理和解析HTML文档，并创建相应的DOM树。本文将深入探讨DOM加载函数的作用、原理及其在Web开发中的应用。 引言 随着互联网的飞速发展，Web技术日新月异。DOM作…...
[特殊字符]《Curve DAO 系统学习目录》
本教程旨在系统学习 Curve DAO 项目的整体架构、核心机制、合约设计、治理逻辑与代币经济等内容，帮助开发者全面理解其设计理念及运作方式。 目录总览： 1. Curve 项目概览 • 1.1 Curve 是什么？主要解决什么问题？ • 1.2 与其他…...
webpack和vite之间的区别
Webpack 和 Vite 都是现代前端开发中非常流行的构建工具，但它们的设计理念、工作原理以及适用场景都有所不同。以下是两者之间详细的对比说明： 1. 构建机制与速度 Webpack: Webpack 是一个通用的模块打包工具，它通过分析项目中的依赖关系图来…...
《Operating System Concepts》阅读笔记：p495-p511
《Operating System Concepts》学习第 44 天，p495-p511 总结，总计 17 页。 一、技术总结 1.cache (1)定义 A cache is a region of fast memory that holds copies of data. (2)cache 和 buffer 的区别 The difference between a buffer and a cac…...
Java进阶——位运算
位运算直接操作二进制位，在处理底层数据、加密算法、图像处理等领域具有高效性能和效率。本文将深入探讨Java中的位运算。 本文目录 一、位运算简介1. 与运算2. 或运算异或运算取反运算左移运算右移运算无符号右移运算 二、位运算的实际应用1. 权限管理2. 交换两个变…...
特征增强金字塔FPN
特征增强金字塔FPN 利用 ConvNet 特征层次结构的金字塔形状，构建一个在所有尺度上都具有强大语义的特征金字塔 总结：特征金字塔是检测不同尺度物体的识别系统中的基本组成部分。 1.利用深度卷积网络固有的多尺度、金字塔层次结构，以边际额…...
Java课程设计（双人对战游戏）持续更新......
少废话，当然借助了ai，就这么个实力，后续会逐渐完善...... 考虑添加以下功能： 选将，选图，技能，天赋，道具，防反，反重力，物理反弹，击落…...
c++第三课（基础c）
1.前文 2.break 3.continue 4.return 0 1.前文 上次写文章到现在，有足足这么多天（我也不知道，自己去数吧） 开始吧 2.break break是结束循环的意思 举个栗子 #include<bits/stdc.h> using namespace std; int main(…...
Windows 图形显示驱动开发-WDDM 2.4功能-GPU 半虚拟化（十一）
注册表设置 GPU虚拟化标志 GpuVirtualizationFlags 注册表项用于设置半虚拟化 GPU 的行为。 密钥位于： DWORD HKLM\System\CurrentControlSet\Control\GraphicsDrivers\GpuVirtualizationFlags 定义了以下位： 位描述0x1 为所有硬件适配器强制设置…...
Android在KSP中简单使用Room
Android在KSP中简单使用Room 最近下载了最新版Studio，好多依赖和配置都需要升级，之前使用过room封装数据库工具类，最近在整理ksp相关，于是把room也升级了，简单记录一下升级过程，直接上代码。 1.添加KSP依…...
Maven 构建配置文件详解
Maven 构建配置文件详解 引言 Maven 是一个强大的项目管理和构建自动化工具，广泛应用于 Java 开发领域。在 Maven 项目中，配置文件扮演着至关重要的角色。本文将详细介绍 Maven 构建配置文件的相关知识，包括配置文件的作用、结构、配置方法等，帮助读者更好地理解和应用 M…...
精确截图工具：基于 Tkinter 和 PyAutoGUI 的实现
在日常工作中，截图是一个非常常见的需求。虽然 Windows 自带截图工具，但有时我们需要更精确的截图方式，比如选取特定区域、快速保存截图并进行预览。本篇博客将介绍一个使用 Python 结合 Tkinter 和 PyAutoGUI 开发的精确截图工具。 C:\pytho…...
Linux练习——有关硬盘、联网、软件包的管理
1、将你的虚拟机的网卡模式设置为nat模式，给虚拟机网卡配置三个主机位分别为100、200、168的ip地址 #使用nmtui打开文本图形界面配置网络 [rootrhcsa0306 ~]# nmtui #使用命令激活名为 ens160 的 NetworkManager 网络连接 [rootrhcsa0306 ~]# nmcli c up ens160 #通…...
【C++】 —— 笔试刷题day_12
一、删除公共字符 题目解析 题目给了两个字符串（其中包含空格），让我们在第一个字符串中删除第二个字符串中的字符。 我们要输出删除后的字符串。 算法思路 这道题，如果直接按照题目中的要求去第一个字符串中删除字符，…...
家乡旅游景点小程序（源码+部署教程）
运行环境 家乡旅游景点小程序运行环境如下： • 前端：小程序 • 后端：无 • IDE工具：微信开发者工具 • 技术栈：小程序 注意：此项目为纯静态项目，无后端 主要功能 家乡旅游景点微信小程序主…...
SQL Server：当在删除数据库时因为存在触发器而无法删除
当在删除数据库时因为存在触发器而无法删除，你可以通过禁用触发器来解决这个问题。下面为你介绍在 SQL Server 里禁用和启用触发器的方法。 禁用数据库中所有表的触发器 你可以使用系统视图 sys.triggers 来查询数据库里所有的触发器，然后生成禁用这些…...
多人协同进行qt应用程序开发应该注意什么2？
在多人协同开发Qt应用程序时，为了确保高效协作、代码一致性和项目可维护性，需要特别注意以下关键点： 1. 版本控制与协作流程 统一版本控制工具：使用Git并规范分支策略（如Git Flow），通过.gitign…...
js关于for of 与for in
for…of for-of循环用于遍历可迭代对象，如数组、字符串、Map、Set等。它直接访问每个元素的值，而不是键名。 const arr [3,5,6,7,0] for(let item of arr){console.log(item); } // 3 // 5 // 6 // 7 // 0只有部署了Iterator接口的数据结构才能使用fo…...
Python Excel
一、Python读Excel——xlrd -*- coding: utf-8 -*- import xlrddef read_excel():打开文件workbook xlrd.open_workbook(rD:\demo1.xlsx)获取所有sheetprint(workbook.sheet_names()) 列表形式返回sheet1_name workbook.sheet_names()[0]根据sheet索引或者名称获取sheet内容…...
前端全局编程和模块化编程
1. 全局编程 <!DOCTYPE html> <html> <head><title>OpenLayers 示例</title><style>.map {width: 100%;height: 400px;}</style><script src"https://cdn.jsdelivr.net/npm/olv7.4.0/dist/ol.js"></script>&…...
随机2级域名引导页HTML源码
源码介绍 随机2级域名引导页HTML源码,每次点进去都随机一个域名前缀。 修改跳转域名在 350 行代码，源码由HTMLCSSJS组成，记事本打开源码文件可以进行内容文字之类的修改，双击html文件可以本地运行 效果预览 源码免费获取 随机2级域名引导页…...
Latex的各种数学公式
Latex的各种数学公式 简介公式1、 A 、 A ‾ \neg A\text{、}\overline{A} A、A2、 、 \text{、} 、3、 ⋅ 、 ∙ \cdot \text{、} \bullet ⋅、∙ 4、表格 简介 这里会随时更新我需要用到的数学公式，以csdn中写作格式为主，可能过时了，不适合…...
稻壳模板下载器（Windows）：免费获取WPS稻壳模板的利器
稻壳模板下载器（Win） 稻壳模板下载器是一款功能强大的工具，能够帮助用户免费下载WPS稻壳儿中的各种模板，无需开通VIP会员。它支持多种模板类型，包括PPT、Word、Excel等，极大地提升了用户的办公效率。 依托…...
BeanDefinition和Beanfactory实现一个简单的bean容器
目录 什么是 Springbean 容器 设计思路 图解 参考文章 开源地址 BeanDefinition 类 BeanFactory 类 测试类 什么是 Springbean 容器 Spring 包含并管理应用对象的配置和生命周期，在这个意义上它是一种用于承载对象的容器，你可以配置你的每个 Bea…...
Mybatis的resultMap标签介绍
说明：在Mybatis中，resultMap 标签可以用于SQL查询后的封装数据，本文用两个场景介绍 resultMap 标签的使用。 搭建环境 先搭一个Demo，pom如下： <?xml version"1.0" encoding"UTF-8"?> &…...
jarvisoj API调用 [JSON格式变XXE]
http://web.jarvisoj.com:9882/ 题目要求：请设法获得目标机器 /home/ctf/flag.txt 中的flag值 抓包得到： POST /api/v1.0/try HTTP/1.1 Host: web.jarvisoj.com:9882 Content-Length: 36 Accept-Language: zh-CN,zh;q0.9 User-Agent: Mozilla/5.0 (W…...
论坛系统的测试
项目背景 论坛系统采用前后端分离的方式来实现，同时使用数据库 来处理相关的数据，同时将其部署到服务器上。前端主要有7个页面组成：登录页，列表页，论坛详情页，编辑页，个人信息页，我…...
RK3588使用笔记：纯linux系统下基础功能配置（不定期更新）
一、前言 用于记录使用RK3588这个平台在纯linux系统下的一些功能配置，RK3588只是一个芯片，linux只是一个系统，但是linux系统可以运行在无数的芯片上，也都大同小异，本编文章主要记录linux系统环境的一些常用的基础功能…...
yum install 报错（CentOS换源）：
yum instally yum utils device mapper persistent-data lvm2 报错： 排查错误原因：centos7 系统停止维护了 解决方案：换源（更换操作系统） //1.备份 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-…...
HTTP常见状态码分析
当浏览者访问一个网页时，浏览者的浏览器会想网页所在的服务器发出请求，当浏览器接收并显示网页前，此网页所在的服务器会返回一个包含 HTTP 状态码的信息头（server header）用以响应浏览器的请求。 常见的状态码…...
Python与Web 3.0支付系统：技术融合与未来展望
Python与Web 3.0支付系统：技术融合与未来展望 随着区块链技术的不断发展，Web 3.0支付系统正逐步成为数字经济的重要组成部分。Python作为一种高效、易用的编程语言，在Web 3.0支付系统的开发中扮演着不可或缺的角色。本文将从技术背景、Python的应用、代码示例以及未来发展趋…...
Linux命令-sed指令
sed命令参数： 基本参数 -n：抑制默认输出，只显示匹配的行。 -e：指定 sed 脚本。 -i：直接修改文件内容。 -f：指定包含 sed 脚本的文件。 -r：启用扩展正则表达式。 常用操作 s：替换字符…...
Unbantu24.04配置-软件安装
Ubantu24.04配置—环境安装 最近在笔记本安装了双系统，这次在这里回顾一下，本章节主要是一些软件的注意点，大多数都是在网上有一定的教程的 1.搜狗输入法 1.1 删除其他框架 sudo apt purge ibus sudo apt remove fcitx5* sudo apt pur…...
八股总结（Java）实时更新！
八股总结（java） ArrayList和LinkedList有什么区别 ArrayList底层是动态数组，LinkedList底层是双向链表；前者利于随机访问，后者利于头尾插入；前者内存连续分配，后者通过指针连接多块不连续的内存…...