C++之BFS深度优先搜索
本文由旧站迁移而来,此后将不再更新此文章。
迁移时间:2024/7/16 15:19:43
提示:本文大部分是手写的,由于手的问题(不想打),大家就看图片把
C++搜索02-BFS
引入&样例1、2讲解
总结
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
例题
1.Luogu B3625 迷宫寻路
题目描述
机器猫被困在一个矩形迷宫里。
迷宫可以视为一个 n * m 矩阵,每个位置要么是空地,要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。
机器猫初始时位于 (1, 1) 的位置,问能否走到 (n, m) 位置。
输入格式
第一行,两个正整数 n,m。
接下来 n 行,输入这个迷宫。每行输入一个长为 $m$ 的字符串,#
表示墙,.
表示空地。
输出格式
仅一行,一个字符串。如果机器猫能走到 (n, m),则输出 Yes
;否则输出 No
。
禁止只输出Yes
或No
骗分!禁止只输出Yes
或No
骗分!禁止只输出Yes
或No
骗分!
样例 #1
样例输入 #1
1 | 3 5 |
样例输出 #1
1 | Yes |
提示
样例解释
路线如下:(1,1)to (2,1) to (3,1) to (3,2)to (3,3) to (2, 3) to (2, 4) to (2, 5) to (3, 5)
数据规模与约定
对于 $100%$ 的数据,保证 1 <= n, m <= 100,且 (1,1) 和 (n, m) 均为空地。
题解(这次真的是我写的了)
P3625 迷宫寻路题解
题意:
我们根据长和宽输入迷宫,判断能否达到$(n,m)$
位置,如果可以输出Yes
,否则输出No
解法:
用BFS进行搜索,搜索可行路线,找到一条去终点的路线
代码:
1 |
|
练习
P1443 马的遍历
题目描述
有一个 n * m 的棋盘,在某个点 (x, y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数,分别为 n, m, x, y。
输出格式
一个 n * m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 -1)。
样例 #1
样例输入 #1
1 | 3 3 1 1 |
样例输出 #1
1 | 0 3 2 |
提示
数据规模与约定
对于全部的测试点,保证 1 <= x <= n <= 400,1 <= y <= m <= 400。
关于
更多练习请见: https://www.luogu.com.cn/training/463808
本文的作者是Minecraft-Sep,本文原创,禁止抄袭!