广度优先搜索实例（广度优先搜索算法实现）



一.bfs是什么

广度优先搜索（Breadth-First Search，简称BFS），是一种图遍历算法。它从给定的起始节点开始，，先访问起始节点的相邻节点，然后再访问相邻节点的相邻节点，以此类推，直到遍历完所有可达节点。

二.基本思路

1.一直往前走，直到到达终点。

2.遇到分岔路口直接分出几条线路分开寻找。

3.遇到死路就直接把那一条路断开。

三.操作步骤

1.数据

假设一个数组a[5][5]，零代表墙，一代表路，初始点是a[1][1]，要到达a[n][n]。

假如数组为：1 0 0 1 1

                      1 1 1 1 0

                      0 0 1 1 1

                      0 1 1 0 1

                      1 1 0 0 1

2.bfs路径

从(1,1)出发，到(2,4)时分成两条线，到(3,4)时又分成两条路线，这时第一次分叉的一条路已经走到头，可以直接结束这个搜索，第二次搜索的第二条线路已经走到终点(5,5)了，可以直接结束循环。

四.代码模板

1.c++模板

2.python模板

3.c模板

五.典型例题

1.洛谷P3395

题目传送门

B 君站在一个n×n 的棋盘上。最开始，B君站在 (1,1)(1,1) 这个点，他要走到 (n,n) 这个点。

B 君每秒可以向上下左右的某个方向移动一格，但是很不妙，C 君打算阻止 B 君的计划。

每秒结束的时刻，C 君 会在 (x,y) 上摆一个路障。B 君不能走在路障上。

B 君拿到了 C 君准备在哪些点放置路障。所以现在你需要判断，B 君能否成功走到 (n,n)。

保证数据足够弱：也就是说，无需考虑“走到某处然后被一个路障砸死”的情况，因为答案不会出现此类情况。

首先是一个正整数 T，表示数据组数。

对于每一组数据：

第一行，一个正整数 n。

接下来 2n−2 行，每行两个正整数 x 和 y，意义是在那一秒结束后，(x,y) 将被摆上路障。

对于每一组数据，输出  或 ，回答 B 君能否走到 (n,n)。

输入 #1

2 2 1 1 2 2 5 3 3 3 2 3 1 1 2 1 3 1 4 1 5 2 2

输出 #1

Yes Yes

样例解释：

以下 0 表示能走，x 表示不能走，B 表示 B 君现在的位置。从左往右表示时间。

数据规模：

防止骗分，数据保证全部手造。

对于 20% 的数据，有 n≤3。

对于 60% 的数据，有 n≤500。

对于 100% 的数据，有 n≤1000。

对于 100% 的数据，有 T≤10。

参考AC代码：

2.洛谷P1332

题目传送门：

巫妖王的天灾军团终于卷土重来，血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团，以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围，现在他们将主力只好聚集了起来，以抵抗天灾军团的围剿。可怕的是，他们之中有人感染上了亡灵瘟疫，如果不设法阻止瘟疫的扩散，很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒，这个叛徒已经投靠了天灾军团，想要将整个血色先锋军全部转化为天灾军团！无需惊讶，你就是那个叛徒。在你的行踪败露之前，要尽快完成巫妖王交给你的任务。

军团是一个 n 行 m 列的矩阵，每个单元是一个血色先锋军的成员。感染瘟疫的人，每过一个小时，就会向四周扩散瘟疫，直到所有人全部感染上瘟疫。你已经掌握了感染源的位置，任务是算出血色先锋军的领主们感染瘟疫的时间，并且将它报告给巫妖王，以便对血色先锋军进行一轮有针对性的围剿。

第 1 行：四个整数 n，m，a，b，表示军团矩阵有 n 行 m 列。有 a 个感染源，b 为血色敢死队中领主的数量。

接下来 a 行：每行有两个整数 x，y，表示感染源在第 x 行第 y 列。

接下来 b 行：每行有两个整数 x，y，表示领主的位置在第 x 行第 y 列。

第 1 至 b 行：每行一个整数，表示这个领主感染瘟疫的时间，输出顺序与输入顺序一致。如果某个人的位置在感染源，那么他感染瘟疫的时间为 0。

输入 #1复制

5 4 2 3 1 1 5 4 3 3 5 3 2 4 

输出 #1复制

3 1 3

输入输出样例 1 解释

如下图，标记出了所有人感染瘟疫的时间以及感染源和领主的位置。

数据规模与约定

对于 100%100% 的数据，保证 1≤n,m≤500，1≤a,b≤105。

参考AC代码：

3.洛谷P7243

题目传送门：最大公约数 - 洛谷

  “寻求最大公约数是人民民主的真谛。……”

  初秋，从枝丫滴下的阳光，柔和，在教室的窗棱溅起，润湿晨读的少女的脸颊。

  “阿绫，阿绫”，天依低俯身子，八字辫耷拉在竖起的课本沿，“我们的最大公约数是多少呢？”

  “一定不小吧”，左手悄悄捏捏天依的小臂，“比如呀，有一个公因子，叫做‘你喜欢我，我也喜欢你’。”

相反，人际圈形形色色，公约数小得可怜，似乎很难保持自己的个性因而变成无趣的人呢。

现在把人际抽象成一个 n×m 的矩形，每个人初始的个性为 ai,j​。从第二天开始，每个人会与上下左右四个人（如果存在）建立人际关系，其个性变为昨天自己和四周人个性的最大公约数。那么对于第 x 行第 y 列的人，在多少天后他的个性会变为 11 呢？

简化题意

有一个 n×m 的矩阵 a。对一个矩阵进行变换，定义为将这个矩阵内的所有元素变为其上下左右四个元素（不存在则忽略）及自身的最大公约数。询问 ax,y​ 在进行最少多少次变换之后会变成 1。如果可以使ax,y​ 经过若干次变换变成 11，输出其中最小的次数；否则输出 −1。

第一行两个整数 n,m，表示矩阵的行数和列数。

接下来 n 行，每行 m 个整数，第 i 行第 j 列的整数 ai,j​ 描述了该位置的人的初始个性。

接下来一行两个整数x,y，表示某个指定的人的位置。

一行一个整数 d，表示第 x 行第 y 列的人的个性会在 d 天后变为 1；特别地，若永远不会变为 1，应输出 −1。

输入 #1复制

2 2 2 2 1 2 2 1

输出 #1复制

0

输入 #2复制

2 2 2 2 2 2 1 1

输出 #2复制

-1

输入 #3复制

3 3 3 2 3 2 3 2 3 2 3 2 2

输出 #3复制

1

样例解释 3

第一天的个性矩阵（也就是最开始的矩阵）为

()⎝⎛​323​232​323​⎠⎞​

第二天的个性矩阵为

()⎝⎛​111​111​111​⎠⎞​

可见只需要经过一天，a2,2​ 就会变为 1，所以答案为 1。

数据规模与约定

本题采用捆绑测试。

对于 100%100% 的数据，1≤n,m≤2×103，1≤ai,j​≤1018，1≤x≤n，1≤y≤m。

参考AC代码：

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/31694.html