HDU 1010 dfs+奇偶剪枝

http://acm.hdu.edu.cn/showproblem.php?pid=1010

这题因为找寻的时间有限，所以用dfs比较直接，另外，还用到了一个犀利的奇偶剪枝

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<math.h>
int n,m,t;
char map[8][8];
int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
int flag;
struct node
{
       int x,y;
}s,e;
int dfs(struct node x,int time)
{
    int a,b,i,j,tt;
    struct node next;
    if(flag==1||(x.x==e.x&&x.y==e.y&&time==t))
    {
        flag=1;
        return flag;
    }
    tt=t-time-(int)fabs(x.x-e.x)-(int)fabs(x.y-e.y);
    if(tt<0||tt&1)//奇偶剪枝，当小于0即会超过，为奇数说明奇偶性不同，没法在规定步骤内恰好到达,偶数和1的&运算结果肯定是0 
      return 0;
    for(i=0;i<4;i++)
    {
      a=x.x+dir[i][0];
      b=x.y+dir[i][1];
      if(a>=0&&a<n&&b>=0&&b<m&&map[a][b]!='X'&&time<t)
      {
         map[a][b]='X';
         next.x=a;
         next.y=b;
         if(dfs(next,time+1))return flag;
         map[a][b]='.';
      }
    }
    return 0; 
}
int main()
{
    int i,j,w;
    char test[10];
    while(scanf("%d%d%d",&n,&m,&t),n||m||t)
    {
       gets(test);
       flag=0;
       w=0;
       for(i=0;i<n;i++)
       {
         gets(map[i]);
         for(j=0;map[i][j]!='';j++)
         if(map[i][j]=='S')
         {s.x=i;s.y=j;map[i][j]='X';}  
         else if(map[i][j]=='D')
         {e.x=i;e.y=j;}
         else if(map[i][j]=='X')w++;
       }
       //for(i=0;i<n;i++)printf("%s
",map[i]);
       if(n*m-w-1<t)
       {
         printf("NO
");
         continue;
       }
       dfs(s,0);
       if(flag)
         printf("YES
");
       else printf("NO
");
    }
    return 0;
}