前言:
* 本帖是讲解BFSBFSBFS的,阅读前需要会编写A+B problem(被删了,所以你得有会编写A+B)的编程石粒,以语文分数不低于0分的石粒
* 为了维持ACGO的风度,所以大部分代码为伪代码,防止有神秘人直接复制粘贴。
* 代码有很多我打比赛保留的一些习惯,可跳过,因为本来就没用
* 废话不多说直接结束开始
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正片
* 1.了解BFSBFSBFS:
* BFS(Breadth−FirstSearch)BFS(Breadth-First Search)BFS(Breadth−FirstSearch),英译:广度优先搜索
* 同事:DFSDFSDFS等
* 核心用处:用于走迷宫(多用于求最短路),遍历图/树等
* 中心思想:“泼水,向四周蔓延”,沿着一个点向外不停延伸,直到不能延伸。
* 拿走迷宫举例(本图选自A8036的样例1)(有点糊,请见谅)
* 看一看这个图,可以发现BFSBFSBFS究竟为何适合求最短路,因为它是由一个点不停向外延伸,所以第一次找到终点那一定就是最短的路
* 2.尝试实现BFSBFSBFS
* 因为BFSBFSBFS是从一个点向外延伸,那么我们需要用一个容器来进行存储遍历,这里推荐用queuequeuequeue——队列(先进先出),进行存储
* 因为BFSBFSBFS大部分用于迷宫,所以这里编写的就仅仅适用于迷宫(因为我真的想不到BFSBFSBFS还可以干啥了)
* 可以封装成函数,但我喜欢不封装,这里就展示不封装的了
* 因为我是甜菜 真的想不到BFSBFSBFS还可以干啥了,随意没有完善代码环节,直接上实战吧!
* 3.实战:
* T1:A8036.走迷宫(没错还是他)
* (1). 分析题目:
* 很朴素的BFSBFSBFS,告诉你地图,让你求从(1, 1) 到 (R, C) 的最短路
* (2). 代码思路:
* 直接用模版即可,注意"计算步数要包括起点和终点"这句话
* (3). 代码实现:
* T2:A8037.腐烂的橘子
* (1). 分析题目:
* 这道题虽然不是走迷宫(终于让我找到了),但是它的题目就是BFSBFSBFS,因为这道题的中心思想是从nnn个点(n = 新腐烂的橘子数)向四周蔓延,感染其他橘子
* (2). 代码思路:
* 利用queuequeuequeue每一次取出它里面原有的所有位置向四周扩散感染
* (3). 代码实现:
* T3:A272.青蛙跳杯子
* (1). 分析题目:
* 不要被这道题的难度唬住了,其实特别简单,说白了就是枚举所有可能,所以DFSDFSDFS可能也能做(吗?)
* (2). 代码思路:
* 枚举出所有目前字符串可以演变的所有可能,我一开始没看清楚,WAWAWA了9次😐
* (3). 代码实现:
* 这题我写了题解,你可以瞅瞅
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3.结尾:
* 目前因时间关系,仅写了一些题目,后面会陆续写一些,同时欢迎投稿题目,如果我写的来我就写,并且会标注投稿人的名字;你也可以补充、纠正,我看到了会改,没看的话你就疯狂**@我**把
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
希望加精
🎉完结撒花🎉