宽搜及应用举例

1、 宽搜及应用 授课人 江苏省扬中高级中学 顾大成例1、最大黑区域（area.?）黑白位图是由黑白两种像素点组成的矩形点阵，图像识别的一个操作是求出黑白位图中最大黑区域的面积。请你设计一个程序完成这个任务。黑区域由黑像素组成，一个黑区域中的每个像素至少与该区域中的另一个像素相邻（仅指上、下、左、右相邻）。两个不同的黑区域没有相邻的像素点。一个黑区域的面积是其所包含的像素点的个数。输入：第一行含两个整数n和m(1=n,mans then ans:=max; end; writeln(ans);end.Const /dx横坐标、dy横纵坐标变化值 dx:array1.4 of longint=(0,

2、1,0,-1); dy:array1.4 of longint=(1,0,-1,0); var a:array0.101,0.101 of longint; max,ans,i,j,n,m:longint;procedure dfs(i,j:longint);var w:longint;begin ai,j:=0; /访问过做标记 max:=max1; for w:=1 to 4 do /往4个方向拓展 if ai+dxw,j+pdyw=1 then dfs(i+dxw,j+dyw);end;JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例1、最大黑区域（area.?）样例输入：5

3、 60 1 1 0 0 11 1 0 1 0 10 1 0 0 1 00 0 0 1 1 11 0 1 1 1 0样例输出：7算法1：dfs 从左上角开始，找到一个黑点（ai,j=1），然后dfs(i,j),dfs到的点置为0，一次dfs完毕得到一个返回值max。主程序中通过打擂台记录最大的max给ans，再找（穷举）下一个点继续dfs。算法2：bfs(宽度优先搜索)_利用队列实现JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用宽度优先搜索（宽搜，bfs)宽度优先搜索算法又称为广度优先搜索，是最简便的图的搜索算法之一，这个算法是很多重要的图论算法的模型；BFS（Breadth Fir

4、st Search）属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻目标节点（目标状态）；换句话说，它并不考虑结果的可能位置，不关心搜索的快慢好坏，就是彻底地搜索整张图，直到找到目标节点为止（或者无解）；从算法的观点看，所有因为展开节点而得到的子节点都会被加入到一个先进先出的队列中，所以是队列的重要应用。JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用通过搜索树，比较bfs与dfs的区别。白色表示未访问的节点，黑色表示已经访问的节点，灰色表示：DFS中为正在访问的节点、BFS中为已入队等待访问的节点。宽度优先搜索（宽搜，BFS)JSOI2017省信息学奥林匹克冬令营基

5、础班教学宽搜及应用结构一：求一个解、所有解、最优解while frontrear then p:=false; end；end;宽度优先搜索（宽搜，bfs)JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例1、最大黑区域（area.?）用bfs怎么做？BFS应用举例 for i:=1 to n do for j:=1 to m do if ai,j=1 then begin front:=1; rear:=1;qf,1:=i; qf,2:=j; ai,j:=0; /从(i,j)开始宽搜 while frontans then ans:=rear; /打擂台求出最优解 end;Var

6、q:array1.10000,1.2of longint;JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例2、瓷砖（tile.?，分班考试）BFS应用举例 在一个w*h的矩形广场上，每一块1*1的地面都铺设了红色或黑色的瓷砖。小Y同学站在某一块黑色的瓷砖上，他可以从此处出发，移动到上下左右四个相邻的、且是黑色的瓷砖上。现在，他想知道，通过重复上述移动所能经过的黑色瓷砖数。输入： 第一行为h、w，2=w、h=50，之间有一个空格隔开； 以下为一个w行h列的二维字符矩阵，每个字符为“.”、“#”、“”，分别表示该位置为黑色的瓷砖、红色的瓷砖、以及小Y的初始位置。输出： 输出一行一个整数

7、，表示小Y从初始位置出发可以到达的瓷砖数。JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用小结1： 以上2个例题，都是说明“宽搜”的一个重要应用：求连通性问题。再比如：usaco中的一个经典题目“数水塘”。BFS应用举例JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例3、关系网络（relationship.?） 有n个人，他们的编号为1n，其中有一些人相互认识，现在x想要认识y，可以通过他所认识的人来认识更多的人（如果a认识b、b认识c，那么a可以通过b来认识c），求出x最少需要通过多少人才能认识y。输入: 第一行三个整数n、x、y；接下来一个nn的邻接矩阵，ai,j=1

8、表示i认识j，ai,j=0表示不认识。保证i=j时,ai,j=0,并且ai,j=aj,i。输出: x认识y最少需要通过的人数。数据保证x一定能认识y 。样例输入：5 1 50 1 0 0 01 0 1 1 00 1 0 1 00 1 1 0 10 0 0 1 0样例输出：2BFS应用举例JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例3、关系网络（relationship.?）算法分析： 宽搜。 先设答案ans=0。把x加入队列并设置为队头元素，从队头开始进行宽搜，穷举邻接矩阵的第x行，看x认识谁（判断ax,j=1），认识的人（j）全部依次入队，并且ans:=ans+1，如果出现了

9、y，则输出ans，结束搜索，否则，取出队头元素继续宽搜。BFS应用举例JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例3用结构一实现：while frontrear then p:=false;/该题此条件可以省略吗？end;BFS应用举例JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用小结2： 本题是说明“宽搜”的另一个重要应用：求最优值问题。比如最少几次、最快几步等！思考：如果要输出x是通过什么关系（哪些人）认识y的呢？解决：再设一个数据域（或者数组），记录当前节点是从哪个节点扩展得到的。BFS应用举例JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例4、迷

10、宫（basic.?） 有一种迷宫,存在如下限制条件：1.迷宫是6*6的；2.迷宫中有3堵平行于x轴或y轴的墙；3.迷宫有一个起点、终点。 如下就是一个例子，图中S和E表示起点和终点。现在的任务是编程找一条从起点到终点的最短路径，但不得越过任何一堵墙。保证有解！BFS应用举例JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用BFS应用举例输入： 第一行、第二行为起点、终点坐标。 第三、四、五行描述3堵墙。前一个坐标一定在后一个坐标的左/上方。输出： 输出一行字符串，用NSEW描述的从起点到终点的最短路径。样例：basic.in1 62 60 0 1 01 5 1 61 5 3 5basi

11、c.outNEEESWW JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例4、迷宫（basic.?）算法分析： 首先要处理好“墙”的问题。把每个格子看成一个“点”，如果点（x,y）和他的上、下、左、右4个相邻点（i,j）之间没有墙，那么他们就可以一步走到，相当于在他们之间连一条边，具体可以用一个“四维数组”表示，即：canx,y,i,j=true，否则设置为false。初始化时，所有的值均为true，同时，为防止出界外围也加上一圈。读入3堵墙，把涉及到的格子两两之间设置为false。再设置一个二维数组v，表示迷宫（起点、终点、该点走没走过）。 由于是要求最短路径，所以，接下来，就是

12、直接的宽度优先搜索了。BFS应用举例JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例5、倒油问题（oil.?） 有3个油瓶，容量分别为10斤、7斤、3斤。开始时，10斤的瓶子中装满了油，其余为空，现在通过在这3个瓶子中倒来倒去，将10斤油分成2个5斤的。请编程输出一种最快的倒油方案。比如：10 0 03 7 03 4 36 4 06 1 39 1 09 0 12 7 12 5 35 5 0BFS应用举例JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例5、倒油问题（oil.?）算法分析： 首先，用一个三元组T（x10,x7,x3）来表示一种状态，其中x10，x7，x3分别

13、表示10斤瓶、7斤瓶、3斤瓶中的油量。 下面，考虑如何实现状态之间的转移。有如下6种倒油的可能性：10斤的瓶子往7斤的瓶子里倒：条件是(x100) and (x70) and (x33) 操作是x10:=x10+x3-3;x3:=3;x7不变7斤的瓶子往3斤的瓶子里倒：?7斤的瓶子往10斤的瓶子里倒：?3斤的瓶子往7斤的瓶子里倒：?3斤的瓶子往10斤的瓶子里倒：?BFS应用举例JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例5、倒油问题（oil.?）算法分析： 第三、在没有找到解（没出现目标状态）之前，是不知道该怎么倒油的，也就是说从当前状态到在一个状态是盲目的，只能穷举。如何穷举

14、、如何保存每一个状态呢？队列！ 第四、由于是要输出最快的倒油方案，所以不应该做无谓的倒油操作，也就是说从一个状态采用一种倒油方法得到的状态不能出现过，否则一定不是最快的倒油方案。所以，需要对状态“判重”。如何实现？穷举！ 第五、因为要输出具体的倒油步骤，所以要保存各个状态之间是怎么转移的，以便找到目标状态后倒过来，按照这个线索输出从初始状态到目标状态。如何实现？再定义一个数据域记录当前节点是从哪个节点扩展得到的，找到目标节点后，倒序把“解路径”上的节点另外保存到一个数组中，最后从初始状态输出到目标状态。 参考程序BFS应用举例JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用1、（ ）

15、是一种先进先出的线性表。A.栈 B.队列 C.哈希表（散列表） D.二叉树2、广度（宽度）优先搜索时，需要用到的数据结构是（ ）。A.链表 B.队列 C.哈希表（散列表） D.栈3、设栈S和队列Q初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该为（ ）。A.2 B.3 C.4 D.5问题讨论（noip初赛试题选讲）BJSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例6、猴群（monkey.?）问题描述: 若某矩形由数学0到9组成，其中数字0代表树，19代表猴子，凡是由0

16、或矩形边围起来的区域表示有一群猴子在这一带。给定数字矩形，求矩形中有多少群猴子。输入:输入数据的第一行为矩形的行数m和列数n，后面为一个mn的数字矩形。输出:输出数据仅一行，一个数，表示猴群的数目。样例输入：4 100234500067103456050020456006710000000089样例输出：4问题讨论JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用0234500067103456050020456006710000000089如果要求最大的猴群中猴群的数量呢？问题讨论JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例7、奇怪的电梯（lift.?） 呵呵，有一天

17、我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1=i=N)上有一个数字Ki(0=Ki=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？输入： 输入文件共有二行，第一行为三个用空格隔开的正整数，表示N、A、B(1N200, 1A,BN)，第二行为N个用空格隔开的正整数，表示Ki。输出： 输出文件仅一行，即最少按键次数,

18、若无法到达，则输出-1。样例输入：5 1 53 3 1 2 5样例输出：3 问题讨论JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用算法分析： 因为要求的是“最少按几次按扭”，所以是很明显的宽度优先搜索。每次从当前结点最多只可以扩展两个结点。问题讨论JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用问题讨论JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用例8、产生数（produce.?） 给出一个整数n（n2000）和k个变换规则（k15）。规则： 1个数字可以变换成另一个数字； 规则中，右边的数字不能为零。 例如：n=234，k=2，规则为 25 36 上面的整数234经过变换后可能产生出的整数为（包括原数）234、534、264、562共4种不同的产生数。求经过任意次的变换（0次或多次），能产生出多少个不同的整数。仅输出不同整数的个数。样例输入：23422 53 6样例输出：4例9、狼羊菜过河问题例10、牧师与野人过河问题问题讨论JSOI2017省信息学奥林匹克冬令营基础班教学宽搜及应用宽搜的缺点：随着搜索层数的增加，空间开销非常大。同时设置两个队列，其中一个队列从初始状态开始拓展，另一个队列从末状态开始拓展，直到两个队列出现交集。双向宽搜能有效地降低时间复