题目大意从S出发,问能否在时间t的时候到达终点D,X为障碍

需要注意的是要恰好在t时刻到达,而不是在t时间之内

深搜,注意剪枝 剩下格子大于t时间的时候剪掉这个很好想,但还是会超时,还有一个剪枝是依靠

奇偶性剪枝

比如地图依靠奇偶性是;

0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1 可以发现偶数走一步一定到奇数,奇数走一步一定到偶数,所以当所在地的奇偶性与目的地D不一样的时候

一定走奇数步子,一样就走偶数步,判断这个来剪枝

code

1 #include 
     
       2 #include 
      
        3 bool flag; 4 int n,m,t,i,j,x1,y1,x2,y2,num; 5 int dix[]={
   1,0,0,-1}; 6 int diy[]={
   0,1,-1,0}; 7 char str[8][8]; 8 void DFS(int k,int l,int tc) 9 {10     int i;11     if(tc==t && k==x2 &&l==y2)12         flag=true;13     if(flag==true) return;14     if (abs(x2-k)+abs(y2-l)>t-tc)return ;  //两个回溯15     if((abs(x2-k)+abs(y2-l))%2!=(t-tc)%2) return;16     for(i=0;i<4;i++)17     {18         int dx=k+dix[i];19         int dy=l+diy[i];20         if(dx>=0 && dx
       
        =0 && dy
        
         =t)60             DFS(x1,y1,0);61         if(flag==true)62             printf("YES\n");63         else64             printf("NO\n");65     }66     return 0;67 }