Tempter of the Bone

这道题啊，折磨了我好久，开始觉得，哦，BFS做就好了，但是范例能过，而实际上却不是合适办法，所以如果对于这道题还是有疑问的同学，只要看看这样一副图就好了。

2 4 7
S..D
....

所以最后参考大神们的代码，解决了本题中的关键问题。

对于奇偶剪枝因为如果对于任何一个位置所在，还需要走的距离是奇数而剩下的时间是偶数，那么可以直接不考虑这条路了，主人公活不了的。直接return掉好了。

所以需要这样来避免时间上被卡住。

代码君

#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;
int   vid[9][9];
char  way[9][9];
int m,n,t;
bool flag = false;
struct Steps{
    int x,y;
};
Steps   walk,en;
const int mov[4][2] = {0,1,0,-1,1,0,-1,0};
void backtrack(int bx,int by,int ust){
    int need;
    if(flag)
        return;
    if(ust == t){
        if(bx == en.x && by == en.y){
            flag = true;
            return;
        }
    }
    need = fabs(bx - en.x)+fabs(by - en.y);
    int temp = t - ust - need;
    if(temp < 0||temp&1){
        return;
    }
    for(int i = 0;i < 4;i++){
        int tx,ty;
        tx = bx + mov[i][0];
        ty = by + mov[i][1];
        if(tx >= 0 && ty >= 0 && tx < n && ty < m && (way[ty][tx] == '.' || way[ty][tx] == 'D') && !vid[ty][tx]){
            vid[ty][tx] = 1;
            backtrack(tx,ty,ust+1);
            vid[ty][tx] = 0;
        }
    }
}
int main(){
    while(~scanf("%d %d %d",&m,&n,&t) && m){
        memset(way,'X',sizeof(way));
        flag = false;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                scanf(" %c",&way[i][j]);
                if(way[i][j] == 'S'){
                    walk.x = j;
                    walk.y = i;
                }
                if(way[i][j] == 'D'){
                    en.x = j;
                    en.y = i;
                }
            }
        }
        memset(vid,0,sizeof(vid));
        vid[walk.y][walk.x] = 1;
        backtrack(walk.x,walk.y,0);
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return  0;
}