全国2019春季noip信息学奥赛普及组讲义PJ D2 基础搜索算法

基础搜索算法 てんご 时光之外的往事 1 勇者sky不知自己身世如何，只是隐约记得父亲说过，他们来自遥远的东方。 但这些都不重要，sky遇上了他命中注定的人——鳴瀬しろは。他也没想到，那宝石蓝的眼眸和雪白的长发会让他如此迷恋。 那一天终于到来了…… 大雾笼罩着森林，朦胧的阳光却显得有些刺眼，喧闹的鸟鸣也消失了，只剩下寂静。 一个巨大的黑影出现了。 “白羽，快，躲到我身后，我来保……” 刹那间，黑影掠过了sky的身旁。勇者感受到了那分明是轻蔑的一瞥。没来得及看清，白羽和黑影一起消失在天空的迷雾中。 “是薮桫岛的黎枔龙……”sky带着一丝惊慌地喃喃道。 于是，勇者sky的传奇拉开了序幕。 Section 0 一无所知者准备踏上征程 了解有关薮桫岛的传说 薮桫岛的由来 薮桫岛本是东方槐荫国的领土，岛上的居民都掌握着搜索之力 但在黎枔龙占领槐荫国之后，就成为了黎枔龙的行宫 黎枔龙对岛民进行了残酷的镇压，并把他们的搜索之力占为己有 搜索之力，被誉为欧艾大陆的无上之力 有云：“不会搜索是万万不能的” 要想打败黎枔龙，也必须拥有强大的搜索之力 那么搜索之力究竟是什么呢？ 这是搜索 这也是搜索 同时截图于 2019.01.26 这是搜索 这也是搜索 搜索之力 在欧艾大陆，每个人都有一只鸽子宠物，人们叫它—— “计算鸡” 不要纠结鸽子为什么叫做鸡（雾 搜索之力是利用计算鸡的高性能 来有目的地穷举一个问题的部分或所有的可能情况 从而求出问题的解的一种方法。 搜索实际上是根据初始条件和扩展规则 构造一棵解答树并寻找符合目标状态的节点的过程。 搜索之力 总而言之 搜索之力就是当人们遇到人脑不能解决的问题的时候， 让计算鸡通过某种方式举出所有可能的解决方法。 从而解决问题的力量 而人们只需要设计这种方式就好啦 Section 1 雄心壮志者拥有了两把神器 “战”和“薱烮” 时光之外的往事 2 sky回到了家中 “父亲，我要去薮桫岛救回白羽！” 本以为支持他成为勇者的父亲会欣然同意，但平日里温和的父亲一听见“薮桫岛”三个字，却迸发出难以言表的愠怒，他抬起了手…… 那一掌始终没有落下 无言的悲凉 命运的无奈 勇者看到了这些 时光之外的往事 2 “sky，你是我唯一的孩子了。“ 这是父亲的最后一句话。 临走前，父亲给了勇者sky两把武器 “战” “薱烮” 栈 “战”，又名“栈” 使用者喊出”stack xxx” 便能在栈的最前端装填一枚xxx弹 是战场随机应变之利器 栈的使用指南 栈的演示 栈的实现 stl/手写 队列 “薱烮”，又名“队列” 使用者喊出”queue xxx” 便能在栈的最后端装填一枚xxx弹 是战场运筹帷幄之利器 队列的使用指南 队列的演示 队列的实现 stl/手写 数据结构 事实上 栈/队列仅仅是数据结构大家庭最简单的一员 还存在许多复杂数十倍的数据结构 当然“现在”的勇者sky还太弱不能驾驭他们的力量 黎枔龙的数据结构水平很高 但是为了剧情需要他现在还不懂数据结构 时光之外的往事 3 长途跋涉总是无趣的 但sky突发奇想 stack cat queue cat shoot! 从此，sky不再孤单 勇者给他们取名“天寒”“地冻” Section 2 刚毅果敢者征战命运之岛 深度优先搜索的应用 迷宫 薮桫岛外被黎枔龙的法阵所笼罩 勇者发现者法阵居然是一个迷宫 它是个w x h的迷宫, #代表障碍 .代表路 只要解决这个迷宫，就能进入薮桫岛 但我们的勇者sky好像是个路痴 天寒、战与DFS 这时候，天寒居然散发出了金光！ “战”将一股强大的力量输送进了sky体内 “随便走，不要走之前走过的路” “走不了就回头一下” 掌握搜索之力 1 勇者发现，那股力量 居然是被黎枔龙夺走的搜索之力！ 于是，勇者sky准备学会使用DFS之力 来继续他的征程 DFS的基本实现 DFS思想 为了求得问题的解 先选择某一种可能情况向前探索 在探索过程中，一旦发现原来的选择是错误的 就退回一步重新选择，继续向前探索 如此反复进行，直至得到解或证明无解。 喜闻乐见的支线剧情 1 勇者翻山越岭 在虾门村遇见了一位苍颜白发的老人yyy “我的麻将台，突然变成了国际象棋盘” “好像有一个我看不懂的问题 你能帮帮我吗？” [Luogu P1219] P1219 八皇后 N x N 的棋盘，放 N 枚皇后 每一行、每一列各有一个皇后 输出3组解，再输出解的总数 N <= 13 喜闻乐见的支线剧情 2 勇者翻山越岭 在侠扪村遇见了一位和蔼可亲的老人yyy “我想玩词语接龙” “可是玩雀魂太久，丧失了实力” “你能帮帮我吗？” [Luogu P1019] P1019 单词接龙 N个单词玩单词接龙 求能接成的最大长度 N <= 20 喜闻乐见的支线剧