宽搜及应用举例.ppt

例5、倒油问题（oil.???） 算法分析： 第三、在没有找到解（没出现目标状态）之前，是不知道该怎么倒油的，也就是说从当前状态到在一个状态是盲目的，只能穷举。如何穷举、如何保存每一个状态呢？队列！ 第四、由于是要输出最快的倒油方案，所以不应该做无谓的倒油操作，也就是说从一个状态采用一种倒油方法得到的状态不能出现过，否则一定不是最快的倒油方案。所以，需要对状态“判重”。如何实现？穷举！ 第五、因为要输出具体的倒油步骤，所以要保存各个状态之间是怎么转移的，以便找到目标状态后倒过来，按照这个线索输出从初始状态到目标状态。如何实现？再定义一个数据域记录当前节点是从哪个节点扩展得到的，找到目标节点后，倒序把“解路径”上的节点另外保存到一个数组中，最后从初始状态输出到目标状态。 参考程序 BFS应用举例 JSOI2017省信息学奥林匹克冬令营基础班教学——宽搜及应用 1、（ ）是一种先进先出的线性表。 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初赛试题选讲） B JSOI2017省信息学奥林匹克冬令营基础班教学——宽搜及应用 例6、猴群（monkey.???） 问题描述: 若某矩形由数学0到9组成，其中数字0代表树，1~9代表猴子，凡是由0或矩形边围起来的区域表示有一群猴子在这一带。给定数字矩形，求矩形中有多少群猴子。 输入:输入数据的第一行为矩形的行数m和列数n，后面为一个m×n的数字矩形。 输出:输出数据仅一行，一个数，表示猴群的数目。 样例输入： 4 10 0234500067 1034560500 2045600671 0000000089 样例输出： 4 问题讨论 JSOI2017省信息学奥林匹克冬令营基础班教学——宽搜及应用 * 宽搜及应用 授课人 江苏省扬中高级中学 顾大成 例1、最大黑区域（area.???） 黑白位图是由黑白两种像素点组成的矩形点阵，图像识别的一个操作是求出黑白位图中最大黑区域的面积。请你设计一个程序完成这个任务。 黑区域由黑像素组成，一个黑区域中的每个像素至少与该区域中的另一个像素相邻（仅指上、下、左、右相邻）。两个不同的黑区域没有相邻的像素点。一个黑区域的面积是其所包含的像素点的个数。 输入：第一行含两个整数n和m(1=n,m=100), 分别表示图像的行数与列数；后面紧跟着n行，每行含m个整数0或1，其中第i行表示图像的第i行的m个像素，0表示白像素，1表示黑像素。每一行的2个数之间有一个空格分隔。 输出：相应的图像中最大黑区域的面积。 JSOI2017省信息学奥林匹克冬令营基础班教学——宽搜及应用 例1、最大黑区域（area.???） 样例输入： 5 6 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 样例输出： 7 JSOI2017省信息学奥林匹克冬令营基础班教学——宽搜及应用 例1、最大黑区域（area.???） 样例输入： 5 6 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 样例输出： 7 算法1:dfs 从左上角开始，找到一个黑点(a[i,j]=1)，然后dfs(i,j)，dfs到的点置为0，一次dfs完毕得到一个返回值max，就是这个黑区域的面积。 主程序中通过打擂台记录最大的max给ans，再找（穷举）下一个黑点继续dfs。 JSOI2017省信息学奥林匹克冬令营基础班教学——宽搜及应用 Begin fillchar(a,sizeof(a),255); readln(n,m); for i:=1 to n do for j:=1 to m do read(a[i,j]); ans:=0; for i:=1 to n do for j:=1 to m do if a[i,j]=1 then //从黑点开始 begin