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

2024-02-18 08:20

本文主要是介绍蓝桥杯备赛_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

相关文章

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Python下载Pandas包的步骤

《Python下载Pandas包的步骤》:本文主要介绍Python下载Pandas包的步骤,在python中安装pandas库,我采取的方法是用PIP的方法在Python目标位置进行安装,本文给大... 目录安装步骤1、首先找到我们安装python的目录2、使用命令行到Python安装目录下3、我们回到Py