学步园

题目链接~~>

                   这题开始用dfs做显然超时，纠结了好久百度了一下，居然用奇偶剪枝（奇偶剪枝是神马！！瞬间蒙了），看了一下代码才明白。。最短时间必须与给定的时间同奇同偶（可画图证明）+给定的时间必须大于最短时间。这题难在奇偶剪枝。。

代码：

#include<stdio.h>
#include<stdlib.h>
int n,m,k,sum ;
char s[8][8] ;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1} ;
void dfs(int x,int y,int bu)
{
    int nx,ny ;
    if(bu==k||sum)
         return ;
     for(int i=0;i<4;i++)
       {
           nx=x+dx[i] ;
           ny=y+dy[i] ;
           if(nx>=0&&nx<n&&ny>=0&&ny<m&&s[nx][ny]!='X'&&bu<k)
            {
                if(s[nx][ny]=='D'&&bu+1==k)
                  {
                        sum=1 ;
                        return ;

                  }
                else if(s[nx][ny]=='.'&&bu+1<k)
                  {
                        s[nx][ny]='X' ;
                        dfs(nx,ny,bu+1) ;
                        s[nx][ny]='.' ;
                  }
            }
       }
}
int main()
{
    int i,j,ex,ey,rx,ry ;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
           if(n+m+k==0)
               break ;
           for(i=0;i<n;i++)
               {
                   scanf("%s",s[i]) ;
                   for(j=0;j<m;j++)
                     if(s[i][j]=='S')
                       {
                           ex=i ;
                           ey=j ;
                       }
                     else if(s[i][j]=='D')
                       {
                           rx=i ;
                           ry=j ;
                       }
               }
               sum=0 ;
        int f=abs(rx-ex)+abs(ry-ey) ;
          if(k>=f&&f%2==k%2)//奇偶剪枝！！！
              {
                  dfs(ex,ey,0);
                  if(sum)
                        printf("YES\n") ;
                  else  printf("NO\n") ;
              }
          else    printf("NO\n") ;
    }
    return 0 ;
}