Hdu1010Tempter of the Bone 深搜+剪枝

题意：输入x,y,t.以及一个x行y列的地图，起点‘S’终点‘D’地板‘.’墙壁‘X’；判断能否从S正好走t步到D。

题解：dfs，奇偶性减枝，剩余步数剪枝。

ps:帮室友Debug的题：打错了两个字母。题目看错。没有初始化map。orz ...不过我dfs也不熟，更别说剪枝了。

//#include <bits/stdc++.h>
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
int n, m, T;
int si, sj, ei, ej;
char a[10][10];
int map[10][10];
int dir[4][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
int check(int i, int j, int t) {
    if (i<0 || i >= n || j<0 || j >= m || map[i][j] || a[i][j] == 'X') return false;

    return true;
}
bool dfs(int i, int j, int t) {
    
    if (i == ei&&j == ej&&t==T) return true;
    if (t>=T) return false;
    map[i][j] = 1;
    for (int k = 0; k<4; k++) {
        int di = i + dir[k][0];
        int dj = j + dir[k][1];
        if (!check(di, dj, t + 1)) continue;
        if (dfs(di, dj, t + 1))
            return true;
        map[di][dj] = 0;
    }
    return false;
}
int main() {
    while (~scanf("%d%d%d", &n, &m, &T)) {
        if (n == 0 && m == 0 && T == 0) break;
        memset(map, 0, sizeof(map));
        for (int i = 0; i<n; i++)
            scanf("%s", a[i]);
        int ok = 0;
        for (int i = 0; i<n; i++) {
            for (int j = 0; j<m; j++) {
                if (a[i][j] == 'D') {
                    ei = i; ej = j;
                    ok++;
                }
                if (a[i][j] == 'S') {
                    si = i; sj = j;
                    ok++;
                }
                if (ok == 2) break;
            }
            if (ok == 2) break;
        }
        if ((T - (abs(ei - si) + abs(ej - sj))) % 2 || (T - (abs(ei - si) + abs(ej - sj)))<0) printf("NO
");
        else if (dfs(si, sj,0)) printf("YES
");
        else printf("NO
");
    }
    return 0;
}