广度优先(BFS)

news/2024/9/11 4:26:08/ 标签: 宽度优先, 算法

先看一道简单的题,迷宫问题:

洛谷P1746 离开中山路:P1746 离开中山路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
#include<cstring>
#include<queue>
#include <utility>
#define N 1002
using namespace std;char g[N][N];
int dist[N][N];
queue< pair<int,int> > q;
int n,x1,y1,x2,y2;int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};void bfs(int x,int y)
{q.push(make_pair(x,y));dist[x][y]=0;while(!q.empty()){pair<int,int> t = q.front();q.pop();for(int i=0;i<4;i++){int a = t.first + dx[i];int b = t.second + dy[i];if(a<1 || a>n || b<1 || b>n) continue;if(g[a][b] != '0') continue;if(dist[a][b] >=0) continue;q.push(make_pair(a,b));dist[a][b] = dist[t.first][t.second] +1;if(a==x2 && b==y2) return ;}}}int main()
{memset(dist,-1,sizeof(dist));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",g[i] +1);}scanf("%d%d%d%d",&x1,&y1,&x2,&y2);bfs(x1,y1);printf("%d",dist[x2][y2]);return 0;
}

先看一下遍历顺序:

可以看出BFS和DFS有着很大的区别,并不是“一条路,走到黑”。而是根据举例根节点的具体进行遍历。

假如先确定顺序是从左到右,那么有什么办法可以从左到右进行遍历呢?

很难想?那就别想了,直接上答案:队列。先进先出啊。

是不是很神奇?


http://www.ppmy.cn/news/1474501.html

相关文章

pandas+pywin32操作excel办公自动化

import pandas as pd import re import win32com.client as win32 from win32com.client import constants import os import os.path as osp #读取表格 pathos.getcwd() fposp.join(path,fuck_demo.xlsx) dfpd.read_excel(fp,header1,usecols[序号,光缆段落名&#xff08;A端…

2024年电子商务与大数据经济国际会议 (EBDE 2024)

2024年电子商务与大数据经济国际会议 (EBDE 2024) 2024 International Conference on E-commerce and Big Data Economy 【重要信息】 大会地点&#xff1a;厦门 大会官网&#xff1a;http://www.icebde.com 投稿邮箱&#xff1a;icebdesub-conf.com 【注意&#xff1a;稿将稿…

PyTorch 2-深度学习-模块

PyTorch 2-深度学习-模块 一: pytorch1> pytorch 介绍2> pytorch 作用3> pytorch 优点4> pytorch 流程二:pytorch 模块1> torch.Tensor 模块2> torch.nn模块3> torch.nn.function模块4> torch.random模块5> torch.onnx模块6> torch.sparse模块7…

原生android的内存性能提升方面的测试和优化方案大致设计

一 测试目标&#xff1a; 以满足用户设备的内存性能和不杀后台为目标。 1&#xff1a;满足用户设备的内存性能是指不出现因为内存原因导致的安卓设备死机&#xff0c;卡顿等问题。 2&#xff1a;满足不杀后台是指整个设备使用时&#xff0c;不出现后台app被杀。 通常是估算如果…

从科幻到现实,IOC如何驱动智慧城市“数字孪生”变革?

每天&#xff0c;世界各地的城市都面临着各种突发事件&#xff0c;这些事件要求跨部门和机构的实时通信及协作。遗憾的是&#xff0c;关键信息通常存储在多个分散的系统中&#xff0c;这阻碍了状况认知&#xff0c;并让各个部门难以协调其响应工作。如果没有单个集成的危机视图…

线程池操作数据库存在线程安全问题

目录 1、前言 2、问题 3、解决方法 3.1、方法一&#xff1a;数据库约束 3.2、方法二&#xff1a;使用锁进行线程的约束 4、总结 1、前言 当前需求为&#xff1a;处理数据&#xff0c;将数据存储到数据库中&#xff0c;在存储的过程中&#xff0c;会先查询该数据是否已经存…

FPGA(1)--什么是布局与布线

布局与布线是FPGA设计流程中非常关键的步骤&#xff0c;它们的目的是将经过综合的逻辑网表映射到FPGA芯片的物理资源上&#xff0c;并通过电气连接来实现设计的功能。具体来说&#xff0c;布局与布线包括以下工作&#xff1a; 布局&#xff08;Placement&#xff09;&#xff1…

9.Python学习:Socket

1.网络通信要素&#xff08;IP端口传输协议&#xff09; 2.Socket编程 2.1TCP、UDP协议了解 2.2 Socket流程 服务端有两个socket对象&#xff0c;客户端有一个 3.Socket实战 服务端代码&#xff1a; import socket #创建Socket对象 sksocket.socket() #绑定ip与端口号-使…

BUG解决:postman可以请求成功,但Python requests请求报403

目录 问题背景 问题定位 问题解决 问题背景 使用Python的requests库对接物联数据的接口之前一直正常运行&#xff0c;昨天突然请求不通了&#xff0c;通过进一步验证发现凡是使用代码调用接口就不通&#xff0c;而使用postman就能调通&#xff0c;请求参数啥的都没变。 接口…

day30--56. 合并区间+ 738.单调递增的数字

一、56. 合并区间 题目链接&#xff1a;https://leetcode.cn/problems/merge-intervals/ 文章讲解&#xff1a;https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html 视频讲解&#xff1a;https://www.bilibili.com/video/BV1wx4y157nD 1.1 初见思路 …

防火墙第一次综合实验

DMZ区内的服务器&#xff0c;办公区仅能在办公时间内(9:00-18:00)可以访问&#xff0c;生产区的设备全天可以访问。 办公区设备10.8.2.1不允许访问DMZ区的FTP服务器和HTTP服务器&#xff0c;仅能ping通10.0.3.10 1.先建立拒绝BG到DMZ区的安全策略 2.建立BG到DMZ区的icmp允许 3…

AI推介-大语言模型LLMs之RAG(检索增强生成)论文速览(arXiv方向):2024.06.01-2024.06.20

文章目录&#xff5e; 1.StackRAG Agent: Improving Developer Answers with Retrieval-Augmented Generation2.FoRAG: Factuality-optimized Retrieval Augmented Generation for Web-enhanced Long-form Question Answering3.Model Internals-based Answer Attribution for T…

springboot仓库管理系统+lw+源码+讲解+调试

第3章 系统分析 在进行系统分析之前&#xff0c;需要从网络上或者是图书馆的开发类书籍中收集大量的资料&#xff0c;因为这个环节也是帮助即将开发的程序软件制定一套最优的方案&#xff0c;一旦确定了程序软件需要具备的功能&#xff0c;就意味着接下来的工作和任务都是围绕…

vue项目实现路由按需加载(路由懒加载)的三种方式

使用异步组件 在使用vue-router配置路由时&#xff0c;可以使用异步组件来实现路由的按需加载。异步组件会在路由被访问时才进行加载&#xff0c;从而实现按需加载的效果。需要注意的是&#xff0c;使用异步组件需要借助webpack的动态import语法来实现。例如&#xff1a; cons…

java 公共字段填充

公共字段填充 1、mybatis-plus2、mybatis 使用注解加aop2.1 自定义注解2.2 自定义切面类2.3 在mapper上添加上自定义的注解 1、mybatis-plus 通过在类上使用如下的注解 TableField(fill FieldFill.INSERT) 是 MyBatis-Plus 中的注解&#xff0c;用于自动填充字段的值。MyBat…

动态规划算法-以中学排课管理系统为例

1.动态规划算法介绍 1.算法思路 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中&#xff0c;可能会有许多可行解。每一个解都对应于一个值&#xff0c;我们希望找到具有最优值的解。动态规划算法与分治法类似&#xff0c;其基本思想也是将待求解问题分解成若…

算法力扣刷题记录 四十【226.翻转二叉树】

前言 继续二叉树其余操作&#xff1a; 记录 四十【226.翻转二叉树】 一、题目阅读 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,6,9] 输出&#xff1a;[4,7,2,9,6,3,1]示例…

three完全开源扩展案例02-跳动的音乐

更多案例尽在https://threelab.cn/ 演示地址 import * as THREE from "three"; import { OrbitControls } from "three/examples/jsm/controls/OrbitControls.js";let mediaElement; let analyser; let scene; let camera; let renderer; let controls; …

DOM(文档对象模型)生命周期事件

前言 DOM 生命周期事件涉及到从创建、更新到销毁 DOM 元素的不同阶段。 ● 我们来看下当HTML文档加载完再执行JavaScript代码 document.addEventListener(DOMContentLoaded, function (e) {console.log(HTML parsed adn DOM tree built!, e); })● 除此之外&#xff0c;浏览…

Electron 简单搭建项目

准备工作 全局安装 node npm创建文件夹&#xff0c;并执行 npm init安装 electron npm i electron --save-dev在 package.json 配置文件中的scripts字段下增加一条start命令&#xff1a; {"scripts": {"start": "electron ."} }由于配置中的入…