HDU 1010 Tempter of the Bone——奇偶剪枝，一道有技巧的dfs题目

这道题的关键在于剪枝，如果没有合理的剪枝，单纯的dfs是会超时的。
这道题的剪枝，用得非常巧妙。
在迷宫中，我们得到起点和终点的横纵坐标，横纵坐标和的奇偶性决定了起点到终点的步数的奇偶性，这是这道题的剪枝关键。
不知道，大家做了这么多迷宫的题目，有没有注意到：从起点到终点，如果起点的横纵坐标和和终点的横纵坐标和的奇偶性相同，那么从起点到终点不管怎么走，都要偶数步，如果奇偶性不同，就一定要奇数步。

AC代码:

#include<iostream>
#include<cstring>
using namespace std;
char maze[10][10];
bool visit[10][10];
int n,m,t,ans;
int startx,starty,endx,endy;
bool flag;
void dfs(int x,int y,int time);
int main()
{
    while(scanf("%d %d %d",&n,&m,&t)!=EOF)
    {
        if(n==0)
            break;
        getchar();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                scanf("%c",&maze[i][j]);
                if(maze[i][j]=='S')
                {
                    startx=i;
                    starty=j;
                }
                if(maze[i][j]=='D')
                {
                    endx=i;
                    endy=j;
                }
            }
            getchar();
        }

        flag = false;
        fill(visit[0],visit[0]+10*10,false);
        visit[startx][starty]=true;
        dfs(startx,starty,0);
        printf("%s
",flag?"YES":"NO");
    }
    return 0;
}
void dfs(int x,int y,int time)
{
    if(flag)
        return;
    if(maze[x][y]=='D')
    {
        if(time==t)
            flag=true;
        return;
    }
    //剪枝
    //起点和终点坐标和的奇偶相同，需要偶数步，否则，奇数步
    int temp=t-time-abs(x-endx)-abs(y-endy);
    if(temp<0||temp%2)
        return;
    int dx[4]={-1,0,0,1};
    int dy[4]={0,-1,1,0};
    for(int i=0;i<4;i++)
    {
        int tempx=x+dx[i];
        int tempy=y+dy[i];
        if(tempx<0||tempx>=n||tempy<0||tempy>=m||maze[tempx][tempy]=='X'||visit[tempx][tempy])
            continue;
        visit[tempx][tempy]= true;
        dfs(tempx,tempy,time+1);
        visit[tempx][tempy]=false;
    }
}