ACM程序设计今天，第一讲根据“信息学初学者之家”网站的统计，Ural（俄罗斯的Ural州立大学的简称，那里设立了一个UralOnlineProblemSet，并且支持OnlineJudge。）的题目类型大概呈如下的分布：搜索动态规划贪心构造图论约10%约15%约5%约5%约10%计算几何纯数学问题数据结构其它约5%约20%约5%约25%搜索题特点分析:——摘自《ACM竞赛之新人向导》什么是搜索算法呢？举例分析HDOJ_1238SubstringsSampleInput23ABCDBCDFFBRCD2roseorchid题目分析：说明：再来一道数值型搜索题HDOJ_1239CallingExtraterrestrialIntelligenceAgainInputTheinputisasequenceofatmost2000tripletsofpositiveintegers,delimitedbyaspacecharacterinbetween.Eachlinecontainsasingletriplet.Thesequenceisfollowedbyatripletofzeros,000,whichindicatedtheendoftheinputandshouldnotbetreatedasdatatobeprocessed.Theintegersofeachinputtripletaretheintegerm,thenumeratora,andthedenominatorbdescribedabove,inthisorder.Youmayassume4<m<=100000and1<=a<=b<=1000.OutputTheoutputisasequenceofpairsofpositiveintegers.Thei-thoutputpaircorrespondstothei-thinputtriplet.Theintegersofeachoutputpairarethewidthpandtheheightqdescribedabove,inthisorder.Eachoutputlinecontainsasinglepair.Aspacecharacterisputbetweentheintegersasadelimiter.Noothercharactersshouldappearintheoutput.获取有用信息算法分析面临的问题：深入分析搜索时的技巧：真正的搜索题预备知识——树的遍历（1）先根遍历以上二叉树的先根遍历序列是：？？（2）中根遍历以上二叉树的中根遍历序列是：？？（3）后根遍历以上二叉树的后根遍历序列是：？？（4）层次遍历以上二叉树的层次遍历序列是：？？几个基本概念：初始状态：目标状态：2三、广度优先搜索BFS算法：搜索过程如下：例1、示意图节点的搜索四、深度优先搜索搜索过程如下：DFS算法例、节点搜索示意图小结：HDOJ_1010TempteroftheBoneInputTheinputconsistsofmultipletestcases.ThefirstlineofeachtestcasecontainsthreeintegersN,M,andT(1<N,M<7;0<T<50),whichdenotethesizesofthemazeandthetimeatwhichthedoorwillopen,respectively.ThenextNlinesgivethemazelayout,witheachlinecontainingMcharacters.Acharacterisoneofthefollowing:'X':ablockofwall,whichthedoggiecannotenter;'S':thestartpointofthedoggie;'D':theDoor;or'.':anemptyblock.Theinputisterminatedwiththree0's.Thistestcaseisnottobeprocessed.OutputForeachtestcase,printinoneline"YES"ifthedoggiecansurvive,or"NO"otherwise.要点分析：想到了什么剪枝条件？奇偶性剪枝这个题目没问题了吧？思考：附录：推荐搜索题：课后一定要练习！ACM,天天见！附录：hdoj_1010月下版#include<iostream.h>#include<string.h>#include<stdlib.h>charmap[9][9];intn,m,t,di,dj;boolescape;intdir[4][2]