HDU

题目大意：给出一个N*M的迷宫，迷宫中有一扇门D，只有在T时刻会打开，现在你0时刻位于S，你需要在正好在T时刻到达D，你只能上下左右移动，每次移动耗费1时刻，且同一个位置不能进入两次，问是否能在T时刻刚好到达D处。

范围 1 < N,M < 7， 1 < T < 50，这个范围有点大，直接DFS回溯搜会TLE，我们要加上一个剪枝，这个剪枝十分重要，我们求出起点到终点的距离（横向距离 + 纵向距离），若这个距离为奇数，则时间T必须也要为奇数，否则时间T必须为偶数（其中的道理显而易见），只有这样，你才有可能在T时刻到达D。详情见下面的代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};

int N, M, T, bx, by, ex, ey;
char Map[10][10];
int vis[10][10];

bool dfs(int x, int y, int t){
    if(x == ex && y == ey && t == T) return true;
    if(t >= T) return false;
    for(int i = 0; i < 4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && ny >= 0 && nx < N && ny < M){
            if(vis[nx][ny]) continue;
            if(Map[nx][ny] == 'X') continue;
            vis[nx][ny] = 1;
            if(dfs(nx, ny, t+1)) return true;
            vis[nx][ny] = 0;
        }
    }
    return false;
}

int main(){
    while(scanf("%d%d%d", &N, &M, &T) == 3 && N){
        for(int i = 0; i < N; ++i){
            scanf("%s", Map[i]);
            for(int j = 0; j < M; ++j)
                if(Map[i][j] == 'D') {
                    ex = i;
                    ey = j;
                }else if(Map[i][j] == 'S') {
                    bx = i;
                    by = j;
                }
        }

        //奇偶剪枝
        int dis = abs(bx-ex)+abs(by-ey);
        if(dis%2 != T%2) {
            printf("NO
");
            continue;
        }

        memset(vis, 0, sizeof(vis));
        vis[bx][by] = 1;
        if(dfs(bx, by, 0)) printf("YES
");
        else printf("NO
");
    }
    return 0;
}