NOIP普及讲座2-搜索应用举例.pptx

搜索应用举例 泰州市第二中学附属初中谢志锋 例1 走迷宫 maze in out pas cpp 问题描述 一个迷宫由R行C列格子组成 有的格子里有障碍物 不能走 有的格子是空地 可以走 给定一个迷宫 求从左上角走到右下角最少需要走多少步 数据保证一定能走到 只能在水平方向或垂直方向走 不能斜着走 输入格式 第一行是两个整数 和 1 R C 40 代表迷宫的长和宽 例1 走迷宫 maze in out pas cpp 接下来是 行 每行 个字符 代表整个迷宫 空地格子用 表示 有障碍物的格子用 表示 迷宫左上角和右下角都是 输出格式 输出从左上角走到右下角至少要经过多少步 即至少要经过多少个空地格子 计算步数要包括起点和终点 例1 走迷宫 maze in out pas cpp 输入样例 55 输出样例 9 例1 走迷宫 maze in out pas cpp 状态分析 1 初始状态2 目标状态3 状态转移 例1 走迷宫 maze in out pas cpp 实现 1 深搜2 宽搜 例1 走迷宫 maze in out pas cpp 提高 双向宽搜 例2 数字游戏 sudoku in out pas cpp 问题描述 这天Kendy路过KFC 看到KFC的橱窗上贴着大幅的宣传海报 海报上说 如果能在规定的时间内解决他们提出的问题 就可以获得价值100元的KFC最新款套餐 Kendy当然不想放过这样的机会 他发现题目是这样的 给你一个N N的表格 3 N 10 在表格中事先已经填入了一部分的数字 现在请你的表格中空余的格子里填入1 N范围内的数字 使得整个表格的每一行和每一列都不存在重复的数字 例2 数字游戏 sudoku in out pas cpp 格的每一行和每一列都不存在重复的数字 当然 为了保证公平 所有人拿到的表格都是随机的且标注了时间 这样Kendy就不可能把题目带回去慢慢研究了 因此他想请你帮忙以便在规定时间内能解决这个问题 保证都有解 例2 数字游戏 sudoku in out pas cpp 输入输出样例 例2 数字游戏 sudoku in out pas cpp 样例说明 本题共有两种填法 取其中第一行数值较小的填法 例2 数字游戏 sudoku in out pas cpp 状态分析 1 初始状态2 目标状态3 状态转移 例2 数字游戏 sudoku in out pas cpp 实现 深搜 例3 砝码 scales in out pas cpp 问题描述 已知一个天平 有N 1 N 1000 个已知质量的砝码 所有砝码质量的数值都在31位二进制内 所称物体在天平的某一边 天平另一边加砝码 直到天平平衡 于是此时砝码的总质量就是物体的质量 物体和砝码不能放到同一边 天平能承受的物体的质量不是无限的 当天平某一边物体的质量大于C 1 C 2 30 时 天平就会被损坏 例3 砝码 scales in out pas cpp 砝码按照它们质量的大小被排成一行 并且 这一行中从第3个砝码开始 每个砝码的质量至少等于前面两个砝码 也就是质量比它小的砝码中质量最大的两个 的质量的和 用这些砝码以及这架天平 能称出的质量最大是多少 由于天平的最大承重能力为C 他不能把所有砝码都放到天平上 例3 砝码 scales in out pas cpp 现在告诉你每个砝码的质量 以及天平能承受的最大质量 你的任务是选出一些砝码 使它们的质量和在不压坏天平的前提下是所有组合中最大的 输入格式 第1行 两个用空格隔开的正整数 N和C 第2 N 1行 每一行仅包含一个正整数 即某个砝码的质量 保证这些砝码的质量是一个不下降序列 例3 砝码 scales in out pas cpp 输出格式 1行 一个正整数 表示用所给的砝码能称出的不压坏天平的最大质量 输入输出样例 例3 砝码 scales in out pas cpp 问题分析 1 数据规模 2 预处理3 搜索方向4 剪枝 例4 Noip2014寻找道路 road in out pas cpp 问题描述 在有向图G中 每条边的长度均为1 现给定起点和终点 请你在图中找一条从起点到终点的路径 该路径满足以下条件 1 路径上的所有点的出边所指向的点都直接或间接与终点连通 2 在满足条件1的情况下使路径最短 注意 图G中可能存在重边和自环 题目保证终点没有出边 例4 Noip2014寻找道路 road in out pas cpp 请你输出符合条件的路径的长度 输入格式 第一行有两个用一个空格隔开的整数n和m 表示图有n个点和m条边 接下来的m行每行2个整数x y 之间用一个空格隔开 表示有一条边从点x指向点y 最后一行有两个用一个空格隔开的整数s t 表示起点为s 终点为t 例4 Noip2014寻找道路 road in out pas cpp 输出格式 输出只有一行 包含一个整数 表示满足题目描述的最短路径的长度 如果这样的路径不存在 输出 1 例4 Noip2014寻找道路 road in out pas cpp 数据说明 对于30 的数据 0 n 10 0 m 20 对于60 的数据 0 n 100 0 m 2000 对于100 的数据 0 n 10 000 0 m 200 000 0 x y s t n x t 例5 模板 template in out pas cpp 问题描述 在魔方风靡全球之后不久 Rubik先生发明了它的简化版 魔板 魔板由8个同样大小的方块组成 每个方块颜色均不相同 可用数字1 8分别表示 任一时刻魔板的状态可用方块的颜色序列表示 从魔板的左上角开始 按顺时针方向依次写下各方块的颜色代号 所得到的数字序列即可表示此时魔板的状态 例如 序列 1 2 3 4 5 6 7 8 表示魔板状态为 例5 模板 template in out pas cpp 对于魔板 可施加三种不同的操作 具体操作方法如下 A 上下两行互换 如上图可变换为状态87654321B 每行同时循环右移一格 如上图可变换为41236785C 中间4个方块顺时针旋转一格 如上图可变换为17245368 例5 模板 template in out pas cpp 给你魔板的初始状态与目标状态 请给出由初态到目态变换数最少的变换步骤 若有多种变换方案则取字典序最小的那种 输入格式 测试数据包括两行 分别代表魔板的初始状态与终止状态 输出格式 输出满足题意的变换步骤 例5 模板 template in out pas cpp 输入输出样例 例5 模板 template in out pas cpp 康托展开 1 2 3 4 n 表示1 2 3 n的排列如 1 2 3 按从小到大排列一共6个 123132213231312321 代表的数字123456也就是把10进制数与一个排列对应起来 他们间的对应关系可由康托展开来找到 例5 模板 template in out pas cpp 如我想知道321是 1 2 3 中第几个小的数可以这样考虑 第一位是3 当第一位的数小于3时 那排列数小于321如123 213 小于3的数有1 2 所以有2 2 个 再看小于第二位2的 小于2的数只有一个就是1 所以有1 1 1所以小于321的 1 2 3 排列数有2 2 1 1 5个 所以321是第6个小的数 2 2 1 1 0 0 就是康托展开 例5 模板 template in out pas cpp 再举个例子 1324是 1 2 3 4 排列数中第几个大的数 第一位是1小于1的数没有 是0个0 3 第二位是3小于3的数有1和2 但1已经在第一位了 所以只有一个数2 1 2 第三位是2小于2的数是1 但1在第一位 所以有0个数0 1 所以比1324小的排列有0 3 1 2 0 1 2个 1324是第三个小数 例5 模板 template in out pas cpp 康托逆展开 1 2 3 4 5 的全排列 并且已经从小到大排序完毕 1 找出第96个数首先用96 1得到95用95去除4 得到3余23有3个数比它小的数是4所以第一位是4用23去除3 得到3余5 例5 模板 template in out pas cpp 有3个数比它小的数是4但4已经在之前出现过了所以第二位是5 4在之前出现过 所以实际比5小的数是3个 用5去除2 得到2余1有2个数比它小的数是3 第三位是3用1去除1 得到1余0有1个数比它小的数是2 第二位是2最后一个数只能是1所以这个数是45321 例5 模板 template in out pas cpp 2 找出第16个数首先用16 1得到15用15去除4 得到0余15用15去除3 得到2余3用3去除2 得到1余1用1去除1 得到1余0有0个数比它小的数是1有2个数比它小的数是3但由于1已经在之前出现过了