hdu 1010 Tempter of the Bone - c++编程基础

链接：http://acm.hdu.edu.cn/showproblem.php pid=1010

后天就考试了，今天做个题攒个人品。

是道好题，dfs+奇偶剪枝。

之前听说过奇偶剪枝，觉得挺有意思，大意就是A点到B点的路程一定比A点到B点的横坐标之差和纵坐标之差之和大偶数步。

刚拿到题的时候觉得是BFS的题，认为只要从A点到B点的最短路程与比要求小并且与所要求的步数小并且差是偶数即可，

WA了几发后，发现自己理解有误，实际上每个点仅仅能走一次不是可以走过去再走回来，这样我就没法用BFS去实现了，就改成DFS+奇偶剪枝来实现了。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #define PI acos(-1.0) #define maxn 8 #define INF 1<<25 typedef long long ll; using namespace std; char ss[maxn][maxn]; int vv[maxn][maxn]; int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}}; int stx,sty,enx,eny; int xx,yy,lim,l; int rec=0; int cango(int x,int y) { if(x>=0&&x
             
              =0&&y
              
               lim) { return 0; }//走的步骤比限制的多，剪掉 for(int i=0; i<4; i++) { if(cango(x+dir[i][0],y+dir[i][1])) { dfs(x+dir[i][0],y+dir[i][1],rec+1); vv[x+dir[i][0]][y+dir[i][1]]=0; } } } int main() { while(scanf("%d%d%d",&xx,&yy,&lim)) { if(xx==0&&yy==0&&lim==0) return 0; memset(vv,0,sizeof(vv)); for(int i=0; i
               
                lim) printf("NO\n"); //这是奇偶剪枝，不用再DFS过程中去剪，因为很容易理解到的就是起点如何不符合那么走的每一步都不符合，但第一步符合，之后的也一定符合 else { jud=0; dfs(stx,sty,0); if(jud==1) printf("YES\n"); else printf("NO\n"); } } }