数据结构与算法实习 数据结构设计技巧之二 北京大学信息科学技术学院 主讲:张铭、郝丹 zhang [at]net. pku. edu. cn http://www.ipk.pkuedu.cn/pkujpk/course/siig/shixil 2011.8 张箱海橙家腾整類划衫耨绫控与赛掌
数据结构与算法实习 ——数据结构设计技巧之二 北京大学信息科学技术学院 主讲：张 铭、郝 丹 mzhang [at] net.pku.edu.cn http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/ 2011.8 张铭 赵海燕 王腾蛟 宋国杰，《数据结构与算法实验 教程》（国家十一五规划教材），高教社2011年1月
图+算法优化 图搜索和应用 算法优化:全1矩阵
图 + 算法优化 ◼图搜索和应用 ◼算法优化：全1矩阵
图周游 1234567 ############################# 1# # # # POJ 1164 #####一一-#####一--#一--#####一--# 2## 迷官中一共有多少个“非 ##### #####一一一#####一一-#####一一-# 房间?最大的房间有3###### 多大? #一—-######### ##### #一一-# 4## ## 求无向图的连通分支 ############################# (Figure 1) ■染色法(F|oodf|) 每次从未染过的点出发做DFS,将所有经过的点染 成同一颜色。重复上述过程直到所有点都被染色 DFS和BFS皆可
图周游 ◼ POJ 1164 – 迷宫中一共有多少个 房间？最大的房间有 多大？ – 求无向图的连通分支 ◼ 染色法（Floodfill） – 每次从未染过的点出发做DFS，将所有经过的点染 成同一颜色。重复上述过程直到所有点都被染色 – DFS和BFS皆可
图应用1 POJ1376 直径为16的圆形机器人如何 能避过障碍,以最短的时间从 起点到达终点? 移动1格或左转90度或右转90 度都需要一个单位时间 给出起点和终点坐标和初始方 向,求最短时间 问题的本质是? 可达点最短路径
图应用1 ◼ POJ 1376 – 直径为1.6的圆形机器人如何 能避过障碍，以最短的时间从 起点到达终点？ – 移动1格或左转90度或右转90 度都需要一个单位时间。 – 给出起点和终点坐标和初始方 向，求最短时间 – 问题的本质是？ – 可达点最短路径
图应用2 ■贪吃蛇PoJ1324 不能咬到尾巴撞到墙 (1,1) (1,1) Ba B B2 B Figure 2 Sample Input Figure 3 After ore ste p from figure 2
图应用2 ◼ 贪吃蛇 POJ 1324 – 不能咬到尾巴撞到墙