hdoj搜索题集

n久没刷题了,感觉水平退化太多了。。今天开始刷题。
把hdoj以前没做的搜索题做一下
hdu1072 简单题
我的思路:出发点和可重置时间的点没有必要访问两次,其他点可以重复访问。这样不会导致bfs一直进行下去。
其他思路:对于这种点可以重复访问的题,bfs入队时不仅要考虑坐标,还要考虑剩余时间,如果同一个点第二次入队时剩余时间比第一次大于或等于,那么不需要入队,没有意义。

hdoj1426

昨天整个下午写和调试这道题到晚上12点多,外加今天一个小时,终于看到了那个ACcept。感动差点就哭了~
其间经历了WA->TLE->WA->OLE->TLE->WA……长期循环,最终发现时judge函数次里面的if块没加括号,原来以为不加可以的,后来想到不加括号可能使else if接错地方。。

hdoj1584

http://blog.csdn.net/longyuan20102011/article/details/7246994
看了这个结题报告才写出来的。。思路确实挺巧妙的,想到了就很简单。原来自己想的时候是枚举每次可以移动的位置。。要保存很多信息,写起来很麻烦。
思路:用pos[i]=j表示牌面为i的牌在位置j,visit[i]表示牌面为i的牌是否已经移动过
几个要点:
1.一张牌只需移一次,所有总共移九次
2.牌面为i的牌只能移到牌面为i+1的牌上面。
3.要移动牌面为i的牌时,如果i+1、i+2、……、i+k都已经移动过,i+k+1未移动过,那么显然i要移到牌面为i+k+1的牌所在位置(因为此时i+1、i+2、……、i+k肯定在i+k+1这张牌上面)
4.从上一条可以得出:每次移动都是将一张没有移动过的牌移到另一张没有移动过的牌的所在位置,移动过的牌所在位置此时都为空。
5.牌面为i的牌移动之后不需要相应改动pos[i],因为第4条可知,这张牌以后不会再用到
所以可见,每一次枚举要移动哪张牌(未移动过的),至于移动到哪,可以枚举牌面比它大的牌,移到第一张未移动过的牌上面

hdoj1180——诡异的楼梯

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1180
bfs,思路是贪心,如果遇到楼梯,能过则尽量过(对面未访问)。因为走楼梯不用花时间,相当于一分钟走了两步,将楼梯对面的格子(前提:还未访问)在解答树中的深度减小了。注意一种特殊情况,这也是本题的精华。就是说如果遇到楼梯,且对面未访问,但此时无法走过楼梯(楼梯方向不对,楼梯方向可以根据走的分钟数的奇偶性判断),则原地等待。等待的具体编程实现方式是bfs时将自身进队。如果下一分钟楼梯对面的格子=已被访问,则放弃,否则通过楼梯访问之。

hdoj1175——连连看

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1175
用dfs思路比较简单,我用了一个比较土的办法来判是否转弯,就是传入该点的前一点坐标和前前一点坐标,前前一点坐标和该点坐标x、y值分别不等,则说明转弯。
用了一个剪枝,当已经转了两次弯时,判断现在所在点的x、y坐标分别与目标点x、y坐标不等,则说明至少还得转一次才能到达目标点,舍去。
后来在网上看到此题还可以用bfs求解,每次把转这次弯可以到达的所有点入队。

hdoj1495

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1495
终于AC了这道隐式图搜索,得出一些教训,感觉又进步了一点点.
(1)对于隐式图,关键是明确状态表,找到状态扩展的特点和方式
(2)要设置标志数组判重(开始没判重,简单地用入队的状态数量做限制,以为没关系。其实要判重,虽然状态总数是(n+1)*(m+1),但如果不判重,那么前面的状态会重复地进队,而目标状态却迟迟不能进队)
(3)注意标志数组初始化范围(0也要初始化)

hdoj1372

题目连接:acm.hdu.edu.cn/showproblem.php?pid=1372
bfs题,其实就是8×8的棋盘上有一只马,问它从指定格点跳到另一指定格点最少需要跳几次。第一次做bfs题,开始的时候不知道怎么记录深度(跳了几次)。后来终于想到了,只要给队列增加一个depth域,每个格点入队时记录它的depth即可。起始格点的depth=0.如果queue[i]是由queue[j]扩展出来的,则queue[i].depth=queue[j]+1;

hdoj1010

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1010
这道题作为我初学dfs,记一下,虽然很早就看过dfs算法,但是一直没用它做过题,感觉对它的认识停留在表面。所以接下来要多做搜索题。
先记录些本菜鸟的体会:
1.基于dfs的遍历(如图的dfs遍历),也就是访问完一个节点(指对该点相邻状态均已dfs)回溯到搜索树的上一层时,如果不将该节点改回未访问,则只能遍历所有状态仅一次。
2.要尝试所有路径,则必须在回溯时,重新修改访问情况(修改visit数组)
3.在dfs时,可以为dfs增加全局变量depth来记录当前dfs深度(反映到具体的迷宫问题中,就是走了几步)
4.dfs解决的是从起始状态到目标状态是否有可达路径,路径是什么
5.bfs则解决从起始状态到目标状态最短路径是什么
对于这道题,首先确定要用dfs。用bfs是思想性错误,因为题目要求是在t秒时正好到达出口(因为出口只在t秒时打开)
下面是代码:(注意:1.要剪枝;2.我的程序在所有状态之外加了一层初始化为已访问的状态,这样就不必判边界了,并且墙壁也可以看成已访问的状态,不用分离出来特意判断)