hdu-1010 Tempter of the Bone(dfs + 优化)

思路：dfs + 剪枝优化
要点1：当剩余可走步数＜曼哈顿距离时一定无解
要点2：当T - f(曼哈顿距离)为奇数时，一定无解,因为一个点到终点的所有路径走的距离的奇偶性一定是一样的！绕路只能增加偶数的距离值，T - f可以简单的判断奇偶，优化算法

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string.h>
using namespace std;
char mp[8][8];//小狗的迷宫地图！
bool vis[8][8];//小狗的记忆,判断地板有没有走过
int n, m, t;
bool flag;//记录是否有解
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};//四个方向
#define check(xx,yy) (xx >= 0 && xx < n && yy >= 0 && yy < m)//判断小狗是否在迷宫中
int f(int x1,int y1,int x2,int y2){//曼哈顿距离(一点到另一点的最短距离)
    return abs(x1 - x2) + abs(y1 - y2);
}
int sx, sy, dx, dy;
void dfs(int x,int y,int step){//step表示已经走了多少步
    if(flag){
        return;//如果找到答案，一步步退出dfs
    }
    int tmp = t - step - f(x, y, dx, dy);
    //t - step表示剩余能走几步，如果剩余距离小于曼哈顿距离，小狗一定走不出去，所以剪枝
    if(tmp < 0){
        return;
    }
    if(mp[x][y] == 'D'){//走到出口了,无论正确与否都要返回
        if(step == t){
            flag = 1;//找到答案
        }
        return;
    }
    for (int i = 0; i < 4; i++){//向四个方向dfs
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if(check(xx,yy) && mp[xx][yy] != 'X' && !vis[xx][yy]){//如果这个方向是空路!而且没走过!
            vis[xx][yy] = 1;//标记已经走过了
            dfs(xx, yy, step + 1);//找到所有路径
            vis[xx][yy] = 0;//回溯
        }
    }
    return;
}

int main(){
    while(~scanf("%d%d%d",&n,&m,&t)){
        if(n == 0 && m == 0 && t == 0){
            break;
        }
        flag = 0;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                cin >> mp[i][j];
                if(mp[i][j] == 'S'){//标记起点
                    sx = i;
                    sy = j;
                }
                if(mp[i][j] == 'D'){//标记终点
                    dx = i;
                    dy = j;
                }
            }
        }
        memset(vis, 0, sizeof(vis));
        vis[sx][sy] = 1;//标记起点已经走过
        int tmp = t - f(sx, sy, dx, dy);
        if(tmp % 2 != 0){//如果tmp为奇数一定无解
            puts("NO");
            continue;
        }
        dfs(sx,sy,0);//搜索所有情况
        if(flag){
            puts("YES");
        }
        else{
            puts("NO");
        }
    }
    return 0;
}