蓝桥杯备赛_python_BFS搜索算法_刷题学习笔记

2024-02-18 08:20
文章标签 python 学习 笔记 bfs 蓝桥 刷题 搜索算法 杯备赛

本文主要是介绍蓝桥杯备赛_python_BFS搜索算法_刷题学习笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 bfs广度优先搜索

1.1 是什么

1.2怎么实现

2案例学习

2.1.走迷宫

 2.2.P1443 马的遍历

2.3. 九宫重排（看答案学的，实在写不来）

 2.4.青蛙跳杯子（学完九宫重排再做bingo）

2.5. 长草

 3.总结

1 bfs广度优先搜索

【Python搜索算法】广度优先搜索（BFS）算法原理详解与应用，示例+代码_广度优先算法的路径搜索代码-CSDN博客

1.1 是什么

        看了其他大佬的分享之后，我理解的广度优先搜索是一种图遍历的算法，简单来说是他的访问规则是一层一层的访问，先访问距离节点近的数据，再逐层拓展访问远的数据。与广度优先搜索密切相关的数据类型叫做队列。队列我们可以理解为是日常生活中排队所形成的队形，先进先出是队列最大的特点。

1.2怎么实现

BFS算法的步骤如下：

  1. 初始化：选择一个起始节点，将其标记为已访问，并将其放入队列中（作为起始节点）。
  2. 进入循环：重复以下步骤，直到队列为空。 a. 从队列中取出一个节点。 b. 访问该节点。 c. 将所有未访问的相邻节点加入队列。 d. 标记已访问的节点，以避免重复访问。
  3. 结束循环：当队列为空时，表示已经遍历完整个图。

算法原理：

        BFS的工作原理是通过队列数据结构来管理待访问的节点。它从起始节点开始，然后逐一访问该节点的相邻节点，并将它们加入队列。然后，它从队列中取出下一个节点进行访问，以此类推。这确保了节点按照它们的距离从起始节点逐层遍历，因此BFS可以用于查找最短路径。

        BFS是一个宽度优先的搜索，它在查找最短路径等问题中非常有用。它不会陷入深度过深的路径，因为它会优先探索距离起始节点更近的节点。

总结：广度优先搜索一般来说都会有一个队列去存储节点，同时也会有一个数组去记录访问的状态。 

2案例学习

2.1.走迷宫

输入：

5 5 
1 0 1 1 0
1 1 0 1 1 
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5

输出：

8

         说明一下这道题的思路，这道题非常直观体现了BFS，并且是最基本的BFS。那代码的思路是怎么样的呢？我们来捋一下。

        一开始所说的队列其实就是列表，只是用到了队列的特点，也就是说队列其实就是类似于列表，只是这个算法的思路用到了队列的特点，一开始我想得太复杂了，总以为队列是一个很高级的容器，其实简单理解就是列表。

        那根据BFS的算法思路：

  1. 初始化：将迷宫的起点作为起始节点        queue=[(x1-1,y1-1,step)]
  2. 进入循环：循环终止的条件是什么，当列表为空就终止了       while queue:                    怎么取出列表的第一个元素，这个时候就是队列的特点，先进先出，怎么体现在列表中，进去就是存入，出来就是删除      x,y,step=queue.pop(0)                                          这里页需要注意走迷宫有上下左右四个方向对应的就是坐标的变化，这也是我对子节点的一个理解

         同时已经访问过的点也要做好标记

        我当时还有一个特别想不懂的，哈哈哈哈哈哈，想起来感觉自己特别蠢哈哈哈哈哈。

        怎么着，我想着每一个节点都有四个子节点，那意味着线路会不一样，怎么就知道那一个的step是最小的，结果我看到那个判断的出口就一下子大悟了，最短路径嘛，那早点满足出口条件的不就是最短路径嘛

n, m = map(int,input().split())
data = []
d = [[1,0],[-1,0],[0,1],[0,-1]]
for i in range(n):l = list(map(int,input().split()))data.append(l)
x1, y1, x2, y2 = map(int,input().split())
def bfs(x1,y1,step):queue=[(x1-1,y1-1,step)]while queue:x,y,step=queue.pop(0)if x==x2-1 and y==y2-1:return stepfor xx,yy in d:dx = x+xxdy = y+yyif 0<= dx <n and 0<= dy <m and data[dx][dy] :data[dx][dy]=0queue.append((dx,dy,step+1))return -1
print(bfs(x1,y1,0))
 2.2.P1443 马的遍历

做好久了但是还是没有完全通过，怎么办可以帮忙看看嘛 

n, m, x, y= map(int,input().split())
d = [[-1,2],[-2,1],[-2,-1],[-1,-2],[1,2],[2,1],[2,-1],[1,-2]]
data = []
result = [[0 for _ in range(m)]for _ in range(n)]
for i in range(1,n+1):for j in range(1,m+1):data.append([i,j])
from collections import deque
def bfs(x,y,a,b,step,visit):queue = deque([(x,y,step)])while len(queue) != 0:x1, y1, step = queue.popleft()if x1 == a and y1 == b:return stepfor xx,yy in d:dx = x1+xxdy = y1+yyif dx < 1 or dx > n or dy < 1 or dy > m:continueif visit[dx][dy] == 0:visit[dx][dy] = 1queue.append((dx, dy, step + 1))return -1for i,j in data:visit = [[0 for _ in range(m + 1)] for _ in range(n + 1)]visit[x][y] = 1ans = bfs(x,y,i,j,0,visit)result[i-1][j-1] = ans
for i in result:for j in i:print(j,end='\t')print('\n',end='')

2.3. 九宫重排（看答案学的，实在写不来）

6.九宫重排 - 蓝桥云课 (lanqiao.cn)

        我当时自己做的时候就在纠结到底是移动格子还是移动数字，很显然，如果要移动数字那每个数字都需要移动，但是移动格子的话我们只需要对这个格子进行操作就可以了。所以移动格子是最佳方案。

         以下是我自己写的错误代码，真的是错的离谱，纪念一下我稀里糊涂的脑子

start = input()
end = input()map1 = [[0 for _ in range(3)] for _ in range(3)]
map2 = [[0 for _ in range(3)] for _ in range(3)]
k1, k2 = 0, 0
for i in range(3):for j in range(3):map1[i][j] = start[k1]if start[k1] == '.':a, b = i, jk1 += 1
for i in range(3):for j in range(3):map2[i][j] = end[k2]k2 += 1d = [[1,0],[-1,0],[0,1],[0,-1]]def bfs(a,b,step):global map1visit = [[0 for _ in range(3)] for _ in range(3)]queue = [(a,b,step)]visit[a][b] = 1while queue:x, y, step = queue.pop(0)if map1 == map2:return stepfor xx,yy in d:dx = x+xxdy = y+yyif dx<0 or dx>2 or dy<0 or dy>2:continueif visit[dx][dy] == 0:visit[dx][dy] = 1map1[x][y],map1[dx][dy] = map1[dx][dy],map1[x][y]queue.append((dx,dy,step+1))return -1
print(bfs(a,b,0))

         别人大佬的代码代码写的真好

蓝桥杯：九宫格重排【BFS】【Python】_重排九宫问题bfs-CSDN博客

        当然我在别人的代码上加上了一些修改以及注释，主要是得自己看得懂

        我也反思了一下自己写的代码思路和别人的，我在一维和二维的变换上处理的十分混乱，导致自己都不知道到底是个什么事儿，因为我也知道是去移动格子，然后交换，但是我就很混乱。当然我的思路还有一些错误。

        别人的代码思路这一点我真是没想到，就是用字典的键值对去存储每一次移动格子后所形成的新字符串的步数，一旦相等了就可以直接返回。

start = input()
end = input()from collections import deque
def bfs():# 创建容器并初始化# 创建字典存储每次变换字符串的步数dic = {}dic[start] = 0# 创建队列queue = deque()queue.append(start)d = [[1, 0], [-1, 0], [0, 1], [0, -1]]# 进入循环while queue:now_start = list(queue.popleft())# 循环结束出口if "".join(now_start) == end:return dic["".join(now_start)]point = now_start.index('.')# 一维的下标转换为二维下标：# 转换公式：x = index//二维数组的宽度    y = index%二维数组的宽度x = point // 3y = point % 3step = dic["".join(now_start)]for xx,yy in d:dx = x+xxdy = y+yyif dx>=0 and dx<3 and dy>=0 and dy<3:new_start = now_start.copy()# 二维转一维# 转换公式：index = x*二维数组的宽度 + ynew_start[point],new_start[dx*3+dy] = new_start[dx*3+dy],new_start[point]if "".join(new_start) not in dic.keys():# dic.setdefault("".join(new_start),step+1)dic["".join(new_start)] = step+1queue.append("".join(new_start))return -1print(bfs())

 

 知识点笔记：

 2.4.青蛙跳杯子（学完九宫重排再做bingo）

1.青蛙跳杯子 - 蓝桥云课 (lanqiao.cn)

        那学完九宫重排之后写这道题就非常简单了，并且这道题还是一维的，不用转换，其他思路跟九宫重排一模一样。

        题目中所说的三种动作，虽然说是青蛙的跳动，但是把当作杯子的跳动去处理就会简单很多，总之学完九宫重排之后这道题就是很简单了。

start = input()
end = input()from collections import deque
def bfs():d = [1, -1, 2, -2, 3, -3]queue = deque()queue.append(start)dic = {}dic[start] = 0while queue:now_start = list(queue.popleft())point = now_start.index('*')step = dic["".join(now_start)]if "".join(now_start) == end:return dic["".join(now_start)]for xx in d:dx = point+xxnew_start = now_start.copy()if dx in range(0, len(start)):new_start[point], new_start[dx] = new_start[dx], new_start[point]if "".join(new_start) not in dic.keys():dic["".join(new_start)] = step+1queue.append("".join(new_start))return -1print(bfs())

2.5. 长草

0长草 - 蓝桥云课 (lanqiao.cn)

        这道题一开始的思路是想到了非连通图的遍历，然后我就是这么一个思路，先找到一个初始化的点先进行广度优先搜索，只进行K层的搜索，但是我一直都无法找到怎样去把握让搜索测层数是我想要的，不知道这个怎么解决，在这里遇到了大问题，然后再遍历我的地图看看还有没有另外的点需要搜索的。所以这个思路就需要两个数组，一个是队列，一个是记录我的访问状态，但是我并没有解决。

        然后就换了一个思路，将节点先依次入队，再对每一个节点进行广度优先搜索，这个就比较好控制，多少层那我就调用多少次的bfs。这里有一个点就在于我的while循环的出口是与队列的长度有关（或者是说节点的个数），因为队列只有把所有的节点都遍历完成之后才算。

        总之这道题也是一道与之前有着一点区别的，也可以算作是遍历非连通图的一种方法。

n, m = map(int,input().split())
maps = []
for i in range(n):l = list(input())maps.append(l)
k = int(input())from collections import deque
queue = deque()
for i in range(n):for j in range(m):if maps[i][j] == 'g':queue.append((i,j))d = [[1,0],[-1,0],[0,1],[0,-1]]
def bfs():ans = len(queue)while ans:x1, y1 = queue.popleft()for xx,yy in d:dx = x1+xxdy = y1+yy# if dx<0 or dx>=n or dy<0 or dy>=m:#     continuif 0<=dx<n and 0<=dy<m and maps[dx][dy] == '.':maps[dx][dy] = 'g'queue.append((dx,dy))ans -= 1for i in range(k):bfs()
for i in maps:print(''.join(i))

 

 3.总结

学习还在继续，持续学习加油！！！！

这篇关于蓝桥杯备赛_python_BFS搜索算法_刷题学习笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/720586。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
python: 多模块(.py)中全局变量的导入

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别： 当你在一个模块（文件）中使用 global 声明变量时，这个变量只在该模块的全局命名空
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
hdu1254（嵌套bfs，两次bfs）

hdu1254（嵌套bfs，两次bfs）

/*第一次做这种题感觉很有压力，思路还是有点混乱，总是wa，改了好多次才ac的思路：把箱子的移动当做第一层bfs，队列节点要用到当前箱子坐标（x，y），走的次数step，当前人的weizhi（man_x，man_y），要判断人能否将箱子推到某点时要嵌套第二层bfs（人的移动）；代码如下：
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
【Python编程】Linux创建虚拟环境并配置与notebook相连接

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如，在当前目录下创建一个名为 myenv 的虚拟环境： python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行： source myenv/bin/activate 3.与notebook连接 在虚拟环境中，使用 pip 安装 Jupyter 和 ipykernel： pip instal
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程（Gaussian Process，简称GP）是一种概率模型，用于描述一组随机变量的联合概率分布，其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数（或核函数） 1.3 核函数1.4 高斯过程回归（Gauss
阅读更多...
【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

系列文章目录 监督学习：参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归（SAheart.csv） 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2