题目链接：点击打开链接

最开始以为是在t秒内是否能到达door，写成了bfs，一直WA,后面发现是dfs后一直T...,在下实在不知道怎么剪枝了，就去百度了一发，然后发现了这个

 

int dis;                              
        dis=(T-time)-(fabs(x-xd)+fabs(y-yd));    // =剩下的时间-无障碍物下的最短路径 
        if(dis<0||dis%2)  return;                //小于0或为奇数就剪掉

奇偶剪枝，出奇的好用，直接一发AC。至于原理嘛

 

 

 要从S走到D，忽略障碍显然最短路径长度是10，而我们把表格用1,0相间填满，易得无论怎么走，1->0或0->1一定是奇数步，0->0或1->1一定是偶数步。

假设还剩13秒，我们先走掉最短路径的10秒，到达的地方一定是0，再走剩下的3秒，到达的一定是1，所以走不到D，这时候就可以直接剪掉。起点是1，终点是0的情况也是一样的，所以只有当剩下的时间-最短路径是偶数时，才可能在剩下的时间刚好走到终点。

奇偶剪枝详见百度百科：点击打开链接

附上完整代码

#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define CRL(a,b) memset(a,b,sizeof(a))
typedef unsigned long long LL;
typedef  long long ll;

char map[10][10];
bool book[10][10];

int move_y[4]= {0,1,0,-1},
               move_x[4]= {1,0,-1,0},m,n,T,X,Y,Find=0,xd,yd;

void create(int n,int m) {
    for(int i=0; i<n; i++)
        scanf("%s",map[i]);

    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(map[i][j]=='S')  {
                X=i;
                Y=j;
            }
            if(map[i][j]=='D')  {
                xd=i;
                yd=j;
            }
        }
    }
}

void dfs(int x,int y,int time) {
    if(map[x][y]=='D'&&time==T) {
        cout<<"YES\n";
        Find=1;
        return;
    }

    int dis;                              //奇偶剪枝：判断在剩余时间里能否走到终点，不是充要条件
    dis=(T-time)-(fabs(x-xd)+fabs(y-yd));    // =剩下的时间-无障碍物下的最短路径
    if(dis<0||dis%2)  return;                //小于0或为奇数就剪掉

    for(int i=0; i<4; i++) {
        int next_x=x+move_x[i];
        int next_y=y+move_y[i];
        if(next_x<0||next_y<0||next_x>n-1||next_y>m-1||map[next_x][next_y]=='X'||book[next_x][next_y])
            continue;
        else {
            book[next_x][next_y]=1;
            dfs(next_x,next_y,time+1);
            if(Find)  return;
            book[next_x][next_y]=0;
        }
    }
    return;
}

int main() {
    while(~scanf("%d%d%d",&n,&m,&T)) {
        if(n==0&&m==0&&T==0)  break;
        Find=0;
        create(n,m);
        CRL(book,0);
        book[X][Y]=1;
        dfs(X,Y,0);
        if(!Find)
            cout<<"NO\n";
    }
    return 0;
}

还有一开始写错了的bfs,在t秒内能否到达door（未找题测试，仅供参考）

 

#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define CRL(a) memset(a,'X',sizeof(a))
typedef unsigned long long LL;
typedef  long long ll;

struct node {
    int x,y,pre;
} way[50];

int move_y[4]= {0,1,0,-1},
               move_x[4]= {1,0,-1,0},m,n,T;

char map[10][10];

void create(int n,int m) {
    getchar();
    CRL(map);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            scanf("%c",&map[i][j]);
            if(map[i][j]=='S') {
                way[1].x=j;
                way[1].y=i;
                way[1].pre=0;
            }
        }
        getchar();//吸收回车
    }
}

void bfs() {
    int X,Y,front=1,rear=1,m=0,n=1,time=0;
    while(1) {
        for(int i=0; i<4; i++) {
            X=way[front].x+move_x[i];
            Y=way[front].y+move_y[i];
            if(map[X][Y]=='D') {
                cout<<"YES\n";
                return;
            }

            if(map[X][Y]=='.') {
                rear++;
                m++;
                way[rear].x=X;
                way[rear].y=Y;
                map[X][Y]='@';		//用'@'只是调试时看着方便
            }
        }
        front++;
        if(--n==0) {
            if(m==0) {              //找不到一条新的路了
                cout<<"NO\n";
                return;
            } else {
                time++;
                if(time>=T) {       //时间到
                    cout<<"NO\n";
                    return;
                }
                n=m;
                m=0;
            }
        }
    }

}

int main() {
    while(cin>>n>>m>>T&&(n||m||T)) {
        create(n,m);
        bfs();
    }
    return 0;
}