HDU 1010 Tempter of the Bone (DFS+可行性奇偶剪枝)

<题目链接>

题目大意：
一个迷宫，给定一个起点和终点，以及一些障碍物，所有的点走过一次后就不能再走(该点会下陷)。现在问你，是否能从起点在时间恰好为t的时候走到终点。

解题分析：
本题恰好要在某一时刻到达，所以需要用到可行性剪枝中的奇偶剪枝，如果在某一点，它所剩的步数与到终点的最短距离之差是偶数，说明这种情况有可能恰好在规定时刻到达终点，否则不可能，将其剪去。

#include <bits/stdc++.h>

using namespace std;

char mpa[][];

int vis[][];

int n,m,t,sx,sy,ex,ey;

bool fp;

const int dir[][]={,,,,-,,,-};

void dfs(int x,int y,int step){

    if(x==ex&&y==ey&&step==t){fp=true;return;}    //恰好达到终点

    int tmp=t-step-abs(ex-x)-abs(ey-y);    //重要的剪枝，可行性奇偶剪枝

    if(tmp< || tmp&)return;

    if(step>t)return;    //超过规定时间，剪去

    if(fp)return;

    for(int k=;k<;k++){

        int nx=x+dir[k][],ny=y+dir[k][];

        if(nx<||nx>n||ny<||ny>m||vis[nx][ny]||mpa[nx][ny]=='X')continue;

        vis[nx][ny]=;

        dfs(nx,ny,step+);

        if(fp)return;    //已经找到答案，结束分支

        vis[nx][ny]=;

    }

}

int main(){

    while(~scanf("%d%d%d",&n,&m,&t),n||m||t){

        for(int i=;i<=n;i++){

            scanf("%s",mpa[i]+);

            for(int j=;j<=m;j++){

                if(mpa[i][j]=='S')sx=i,sy=j;

                if(mpa[i][j]=='D')ex=i,ey=j;

            }

        }

        memset(vis,,sizeof(vis));

        fp=false;

        vis[sx][sy]=;dfs(sx,sy,);

        fp?puts("YES"):puts("NO");

    }

}