学步园

小记：最开始以为是T时间内，用bfs WA了，后来知道是刚好T时间，然后就用dfs， 相当于暴力了，然后简单的dfs提交TLE， 必须剪枝。

首先判最少需要的时间是否有，没有就不用继续了，而如果有，那么因为我们是要花掉T时间刚好到达，那么我们先保证能走到终点的时间，然后在路上花掉多余的时间

此时，我们必须保证我们多出来的时间必须是偶数，这样我们才能回来，否则就回不来了，回不来就意味着到达不了终点，一来一回两倍距离，所以必须是偶数。

就加上这个剪枝就A了

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-10
#define PI acos(-1.0)//3.14159265

const int MAX_ = 1010;
const int N = 100010;
const int INF = 0x7fffffff;

int mp[MAX_][MAX_];

int dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};

int n,m, T, ex, ey;

int dfs(int x,int y,int step){
    if(mp[y][x] == -1 && step == T){return 1;}

    if(step >= T){return 0;}

    int tmp = abs(x-ey) + abs(y-ex);
    if((tmp > T-step )|| ((T-step-tmp)%2))return 0;

    for(int i = 0; i < 4; ++i){
        int nextx, nexty;
        nextx = x + dir[i][0];
        nexty = y + dir[i][1];
        if((nextx > 0 && nextx <= m) && (nexty > 0 && nexty <= n) && mp[nexty][nextx] != 1){
            int tmp = mp[y][x];
            mp[y][x] = 1;
            int flag = dfs(nextx,nexty,step+1);
            if(flag)return 1;
            mp[y][x] = tmp;
        }
    }
    return 0;
}
/*
7 7 48
S......
.......
.......
.......
.......
.......
......D
*/

int main(){
    int  ans, sx,sy, cnt;
    char c;
    //freopen("E://1.txt","w",stdout);

    while(scanf("%d%d%d",&n,&m,&T), n||m||T){
        getchar();
        cnt = 1;
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                scanf("%c",&c);
                if(c == 'S'){
                    sx = i, sy = j;
                    mp[i][j] = 1;
                }
                else if(c == '.'){
                    mp[i][j] = 0;
                }
                else if(c == 'X'){
                    cnt++;
                    mp[i][j] = 1;
                }
                else if(c == 'D'){
                    ex = i, ey = j;
                    mp[i][j] = -1;
                }
            }
            getchar();
        }

        if((abs(ex-sx) + abs(ey-sy) > T) || (n*m - cnt < T)){
            ans = 0;
        }
        else ans = dfs(sy,sx,0);
        if(ans)
            printf("YES\n");
        else
        printf("NO\n");

	}
	return 0;
}