- 2024-10-28算法学习笔记2:搜索
搜索BFS我的理解:基础的bfs本质上也是动态规划,dist[i,j]表示到达(i,j)转移的最小次数。由于动态规划的无后效性,就是当前状态确定后,不需要管之前的状态转移。bfs是一层一层搜的,搜索的相当于是一个状态,第一个搜到的就是最优的。比如最简单的走迷宫,每个点只会走一次,那么第一
- 2024-10-23【SSL 1823】消灭怪物(非传统BFS)
题目大意小b现在玩一个极其无聊的游戏,它控制角色从基地出发,一路狂奔夺走了对方的水晶,可是正准备回城时,发现地图上已经生成了n个怪。现在假设地图是二维平面,所有的怪和角色都认为是在这个二维平面的点上。请你帮小b计算一下,从现在角色的位置开始,至少要消灭几个怪才能回到基地(坐
- 2024-10-23DFS与BFS
图论:一、图中DFS与BFS数和图的存储方式:m与n^2一个级别属于稠密图,m与n一个级别则属于稀疏图,可以从题目中明显看出来稠密图:邻接矩阵稀疏图:邻接表#include<bits/stdc++.h>usingnamespacestd;constintN=100100;intm,n;inth[N],e[N],ne[N],idx;intq[N],d[N];bool
- 2024-10-22【头歌实训:邻接表存储图的广度优先遍历】
头歌实训:邻接表存储图的广度优先遍历文章目录任务描述相关知识邻接表存储图图的遍历广度优先遍历过程:算法设计思路:编程要求测试说明输入格式:输出格式:样例输入:样例输出:源代码:任务描述相关知识邻接表存储图图的遍历广度优先遍历过程:算法设计思路:
- 2024-10-21AT_abc348_d [ABC348D] Medicines on Grid 题解
题目传送门题目大意:给定一个\(n\timesm\)的地图,要求从起点S走到终点T,每移动\(1\)个会消耗\(1\)点能量,障碍#不能走,空地为.可以走,体力消耗至\(0\)也无法移动,地图位置\((x_i,y_i)\)有一瓶可以变成\(e_i\)体力的药,可以选择是否喝。问能否抵达终点,可以输出Yes,否
- 2024-10-2020241020比赛总结
T1Reversehttps://www.gxyzoj.com/d/hzoj/p/P980假设1在点i时,这个1可以通过一次翻转到达那些点,将这些点和i连边,此时答案就是s到x的最短路但是,此时边数也会到达\(n^2\)级别考虑优化,因为边权均为1,所以可以直接bfs,可以发现每个点能转移的点的奇偶性是有限制的,而且每个点至多被更
- 2024-10-20Leetcode 1926. 迷宫中离入口最近的出口
1.题目基本信息1.1.题目描述给你一个mxn的迷宫矩阵maze(下标从0开始),矩阵中有空格子(用‘.’表示)和墙(用‘+’表示)。同时给你迷宫的入口entrance,用entrance=[entrancerow,entrancecol]表示你一开始所在格子的行和列。每一步操作,你可以往上,下,左或者右移动一
- 2024-10-1801 bfs 学习笔记
当一张图的边权只有\(0\)和\(1\)时,跑dij的堆优化显得比较累赘。因为只有两个取值,所以取\(0\)的时候在队列前面推进来,反之在后面。其他和dij没什么区别,时间复杂度\(O(m)\),其中\(m\)是边数。相关题目:P4554小明的游戏。点击查看代码voidwork(){ m0(vis);mem(di
- 2024-10-18二维 bfs 基础笔记
一、寻找连通块1.基本思路找到一个未被走过的点,以这个点为起点,将与此点相连的所有点标记为走过,答案数\(+1\)2.代码实现#include<bits/stdc++.h>usingnamespacestd;structp{intx,y;};queue<p>q;intn,m,cnt;//最终答案为cntintdx[]={1,-1,0,0}
- 2024-10-1610/16 牛客
第一道题这是我第一次做bfs广度搜索的题简单了解了一下广度优先搜索的概念就是从一个点开始寻找邻居节点然后再从邻居节点开始找未被访问过的邻居节点,最后都被访问了且是最短路径算法我看视频里是利用队列实现的利用队列先进先出的性质确保对头的点出去以后是剩下的邻居
- 2024-10-10算法笔记(十五)——BFS 解决拓扑排序
文章目录拓扑排序课程表课程表II火星词典拓扑排序有向无环图(DAG图)有向无环图指的是一个无回路的有向图AOV网:顶点活动图在有向无环图中,用顶点表示一个活动,用边来表示活动的先后顺序的图结构拓扑排序找到一个先后顺序,结果可能不唯一如何拓扑排序?找到一
- 2024-10-092024.10.9 LGJ Round
B对于所有\(x\in[0,n],y\in[0,m]\),求执行\(x\getsx+y,y\getsx+y\)若干次后满足\(x=k\)的双元组个数。这个题充分体现我的唐氏。具体地枚举\(x,y\)分别被算了多少次,系数是斐波那契数列,所以项数很少。然后转化为求\(k_1x+k_2y=k\)的方案数,这个我非常唐不会求。只需
- 2024-10-09二叉树 学习
1.1 理解递归104,二叉树的最大深度“使用BFS求解”100,相同的树101,对称的树110,平衡二叉树199,二叉树的右视图236.二叉树的最近公共祖先235.二叉搜索树的最近公共祖先1.2二叉树遍历144.二叉树的前序遍历94.二叉树的中序遍历145.二叉树的后序遍历102.二叉树的
- 2024-10-07数据结构课程设计大项目————迷宫问题(邻接矩阵,prim生成算法,DFS寻路,BFS寻路,路径回溯)
一.前言迷宫问题是数据结构中最值得实践的大项目之一,本文主要讲解思路,提供的代码大部分都有注释(没有的就是太多了懒得写了QAQ)。为了更好的表现效果,该程序使用了easyx可视化,easyx简单易学(大概一天到两天就可以学会),上手简单。该程序由c语言实现,本人水平有限程序可优化空间很大。
- 2024-09-309073 关系网络 广搜 队列
解决思路 广度优先搜索 (BFS):使用BFS从起点 x 开始搜索,找到到达终点 y 的最短路径。 队列:使用队列存储当前节点和步数。 访问标记:使用数组 vis 标记节点是否被访问过,防止重复访问。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;c
- 2024-09-29一维BFS模型
算法竞赛题目中有一种常见的一维BFS模型。这种模型的特点是,某一个状态的值可以有上一个状态的值+1来获得(也就是说一条通道的权重是1)。比如例题:农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点 N,牛位于点 K。农夫有两种移动方式:从 X 移动到X−
- 2024-09-29深度DFS 和 广度BFS搜索算法学习
深度DFS和广度BFS搜索算法学习 目录广度优先的动态图深度优先的动态图广度和深度的具体步骤深度和广度的应用场景 图的两种遍历方式:深度优先遍历(DFS——DepthFirstSearch)广度优先遍历(BFS——BreathFirstSearch)图的遍历算法里,处理临时数据,依赖两个抽象
- 2024-09-28【图计算算法】广度优先搜索(BFS)算法
目录一、广度优先搜索算法概述1.1算法原理1.2算法步骤1.3算法特点二、广度优先搜索算法优缺点和改进2.1 广度优先搜索算法优点2.2 广度优先搜索主算法缺点2.3 广度优先搜索算法改进三、广度优先搜索算法编程实现3.1 广度优先搜索算法C语言实现3.2
- 2024-09-25bfs 与优先队列————洛谷p1126(历经两个小时总算AC了,哭晕)
机器人搬重物题目描述机器人移动学会(RMI)现在正尝试用机器人搬运物品。机器人的形状是一个直径\(1.6\)米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个\(N\timesM\)的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时
- 2024-09-24bfs与优先队列 [NOIP2017 普及组] 棋盘————洛谷p3956
[NOIP2017普及组]棋盘题目背景NOIP2017普及组T3题目描述有一个\(m\timesm\)的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的),你只能向上、下、左、右
- 2024-09-23简单搜索(BFS,DFS,剪枝)一网打尽
深搜DFS含义深搜是一种遍历或搜索图和树的算法。实现方式(不撞南墙不回头)根据题目选择一个适合的源节点,从源节点开始选择一条路一直走,直到无法前进(不满足题目条件)时,返回到上一个节点重新尝试,直到当前的节点的所有子节点都已经被访问过,再次返回到当前节点的上一节点,继续重复
- 2024-09-22BFS 马的遍历————洛谷p1443
马的遍历题目描述有一个\(n\timesm\)的棋盘,在某个点\((x,y)\)上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。输入格式输入只有一行四个整数,分别为\(n,m,x,y\)。输出格式一个\(n\timesm\)的矩阵,代表马到达某个点最少要走几步(不能到达则输出\(-
- 2024-09-21BFS 颜色填涂———洛谷p1162
填涂颜色题目描述由数字\(0\)组成的方阵中,有一任意形状的由数字\(1\)构成的闭合圈。现要求把闭合圈内的所有空间都填写成\(2\)。例如:\(6\times6\)的方阵(\(n=6\)),涂色前和涂色后的方阵如下:如果从某个\(0\)出发,只向上下左右\(4\)个方向移动且仅经过其他\(0\)的情况下
- 2024-09-20深入探索:深度优先遍历与广度优先遍历的奥秘与应用
在算法和数据结构的广阔领域中,图的遍历是一个核心且基础的概念,它支撑着众多高级算法和应用的实现。深度优先遍历(DFS)和广度优先遍历(BFS)作为图的两种基本遍历方式,不仅具有深刻的理论意义,还广泛应用于各种实际问题中。本文将更深入地探讨这两种遍历方式的原理、实现细节、性能
- 2024-09-14bfs与dfs ,全球变暖——蓝桥problems178
问题描述:........##.....##........##...####....###........有一张还以N*N的像素照片,“.”表示海洋,“#”表示陆地,其中上下左右能连在一起的陆地称作岛屿,例如上图有两座岛屿,由于全球气候变暖,靠经海洋的陆地会被淹没,问图中有多少座岛屿会被完全淹没....................