hdu 1010 Tempter of the Bone 深搜+剪枝

hdu 1010 Tempter of the Bone 深搜+剪枝

题意：在一个坐标内，给定起点和终点，问能否恰好在t时刻到达终点。

以前很少写搜索题，所以看到这个题，就按照普通的深搜写了一下，交上去超时了。后来在网上搜了一下才知道，要剪枝才行。可是，我以前从没写过剪枝，不知道怎么剪，就按照别人的思路往下想。看懂以后，我对剪枝的理解是：对于一些没有必要继续搜索的路径，不再往下深搜，提前返回到上一层。花了半天时间调试代码，终于AC了。

奇偶剪枝：根据题目，doggie必须在第t秒到达门口。也就是需要走t-1步。设doggie开始的位置为（sx,sy）,目标位置为（ex,ey）.如果abs(ex-x)+abs(ey-y)为偶数，则abs(ex-x)和abs(ey-y)奇偶性相同，所以需要走偶数步；

当abs(ex-x)+abs(ey-y)为奇数时，则abs(ex-x)和abs(ey-y)奇偶性不同，到达目标位置就需要走奇数步。先判断奇偶性再搜索可以节省很多时间，不然的话容易超时。t-sum为到达目标位置还需要多少步。因为题目要求doggie必须在第t秒到达门的位置，所以（t-step）和abs(ex-x)+abs(ey-y)的奇偶性必然相同。因此temp=（t-step）-abs(ex-x)+abs(ey-y)必然为偶数。

#include#includeint flag,sx,sy,ex,ey,num;int n,m,t,vis[10][10];int dx[]={-1,0,1,0};int dy[]={0,-1,0,1};char map[10][10];int abs(int p){ return p>=0?p:-p;}void dfs(int x,int y,int sum){ int i,xx,yy; if(flag==1) return ; if(x==ex&&y==ey&&sum==t) { flag=1; return ; } int mindis=abs(x-ex)+abs(y-ey); if(mindis>t-sum||(mindis+t-sum)%2!=0) return; for(i=0;i<4;i++) { xx=x+dx[i]; yy=y+dy[i]; if(xx>=0&&xx=0&&yy

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。