信息学奥赛宽搜和应用.ppt

四、宽度优先有哪些信誉好的足球投注网站的算法应用 [例2] 小明抄答案 有一次上数学课，老师布置了课堂作业。小明在写作业时睡着了。他梦见自己站在一个迷宫里，一个圣人给了他迷宫的地图，说：“你现在位于迷宫的左上角，迷宫的右下角有数学作业的答案。你只能上下左右走，但你放心，我没有耍你，迷宫是一定能走得通的。”小明很想拿到答案，但他太笨了 ，所以找来了会编程的你，叫你 帮他找到答案。他需要知道找到 答案的最少步数。 四、宽度优先有哪些信誉好的足球投注网站的算法应用 [例2] 小明抄答案 【输入】 第一行是两个整数，Ｒ和Ｃ，代表迷宫的行数和列数（2=R,C =100）。接下来的Ｒ行，每行Ｃ个字符，代表整个迷宫。空地格子用.表示，有障碍物的格子用#表示。迷宫左上角和右下角都是.。 【输出】 一行包含一个整数，输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。注：计算步数要包括起点和终点。 四、宽度优先有哪些信誉好的足球投注网站的算法应用 [问题分析-小明抄答案] 状态表示： 初始状态： 目标状态： (1,1) (r,c) 1 1 Start End r c 当前所在迷宫的位置（行号, 列号） 左上角 右下角 四、宽度优先有哪些信誉好的足球投注网站的算法应用 [问题分析-小明抄答案] 状态转移： 转移规则： 约束条件： 1 = x = r 1 = y = c ④ ③ (x,y) ① ② ① (x,y+1) ② (x+1,y) ③ (x,y-1) ④ (x-1,y) 四、宽度优先有哪些信誉好的足球投注网站的算法应用 [问题分析-小明抄答案] 1 2 3 4 5 6 7 8 9 1 1 1 行号 最少步数 1 2 3 4 1 ● ● # # 2 # ● ● # 3 # ● # ● 4 # ● ● ● 列号 (1,1) (1,2) (2,2) (2,3) (3,2) (4,2) (4,3) (4,4) 1 2 2 2 2 3 2 3 4 3 2 4 4 2 5 4 3 6 4 4 7 找到目标状态 四、宽度优先有哪些信誉好的足球投注网站的算法应用 [问题分析-小明抄答案] 思考：如果要输出其中一条最短路径，怎么办？ 1 2 3 4 5 6 7 8 1 1 2 2 3 4 4 4 1 2 2 3 2 2 3 4 1 2 3 4 4 5 6 7 0 1 2 3 3 5 6 7 行号 最少步数 列号 前驱节点 (1,1) ?(1,2)?(2,2)?(3,2)?(4,2)?(4,3)?(4,4) 1 2 3 4 1 ● ● # # 2 # ● ● # 3 # ● # ● 4 # ● ● ● 四、宽度优先有哪些信誉好的足球投注网站的算法应用 第二类应用：求连通块问题 四、宽度优先有哪些信誉好的足球投注网站的算法应用 [例3] 宝岛探险 【题目描述】 某海域航拍图由一个R行C列的数字矩阵组成，图中数字表示海拔，0表示海洋，1~9表示陆地。求该海域共有多少岛屿，最大的岛屿面积多大（即包含多少格子）。我们把上下左右相邻接的陆地视为同一岛屿。 四、宽度优先有哪些信誉好的足球投注网站的算法应用 [例3] 宝岛探险 【样例输入】 【样例输出】 4 10 4 11 0234500067 1034560500 2045600671 0000000089 【数据范围】 1= R，C = 20 四、宽度优先有哪些信誉好的足球投注网站的算法应用 [问题分析-宝岛探险] 求连通块问题的基本思路是：从某关键点（不是海洋的点）开始BFS，形成的连通区域即为一连通块。 四、宽度优先有哪些信誉好的足球投注网站的算法应用 [问题分析-宝岛探险] 1 2 3 4 5 6 7 8 9 10 1 0 2 3 4 5 0 0 0 6 7 2 1 0 3 4 5 6 0 5 0 0 3 2 0 4 5 6 0 0 6 7 1 4 0 0 0 0 0 0 0 0 8 9 每找到一个岛屿，个数就+1 四、宽度优先有哪些信誉好的足球投注网站的算法应用 [问题分析-宝岛探险] 1 2 3 4 5 6 7 8 9 10 11 1 2 1 2 3 4 5 6 7 8 9 10 1 0 2 3 4 5 0 0 0 6 7 2 1 0 3 4 5 6 0 5 0 0 3 2 0 4 5 6 0 0 6 7 1 4 0 0 0 0 0 0 0 0 8 9 1 3 1 4 2 3 1 5 2 4 3 3