本题就是考剪枝法了。
应该说是比较高级的应用了。因为要使用heuristic（经验）剪枝法。要总结出这个经验规律来，不容易。我说这是高级的应用也因为网上太多解题报告都没有分析好这题，给出的程序也很慢，仅仅能过掉，由此看来很多人没有做好这道题。
这里我需要更正一下网上流行的说法：奇偶剪枝法。
其实本题使用奇偶剪枝法并不能太大提高速度，只能说仅仅让使用奇偶剪枝过掉。所以网上说本题使用奇偶剪枝的，其实并不能提高速度。
原因：
奇偶剪枝只能剪枝一次，不能在递归的时候剪枝，因为只要初始化位置符合奇偶性，那么之后的任意方格都会符合奇偶性。
故此理论上也是不能提高速度的，当然本人也实验过多次，证实奇偶剪枝至少对本题来说用处不大。
本题的主要剪枝法应该是一条： 最大空格数和步数比较。就是说如果生下的空格数位grids，而需要走T步，grids < T的时候，就可以判定为NO了。
当然还有第二条剪枝：如果当前位置到目标位置最少需要steps步，而需要走T步，那么steps > T，就可以判定为NO了。
不过事实证明只需要使用第一个剪枝法就可以了。
第二条剪枝用处也不大，原因：递归的格子很少，计算距离差并不能提高多少速度。
如我下面递归循环中只使用一条主要剪枝就足够了，不超100ms。虽然没有做到0ms，不过速度已经是够快的了。
0ms估计需要进一步的剪枝，有大牛，请指教一下。有空要深入研究一下A*算法才行了。
int sr = 0, sc = 0, dr = 0, dc = 0, n, m, grids, Tsec;
vector<string> maze;
bool escapeMaze()
{
if (sr == dr && sc == dc)
{
if (Tsec == 0) return true;
return false;
}
if (grids < Tsec) return false;
if (Tsec == 0) return false;
maze[sr][sc] = '$';
grids--; Tsec--;
if (sr+1 <(int)maze.size() && maze[sr+1][sc] == '.')
{
sr++;
if (escapeMaze()) return true;
sr--;
}
if (sc+1 < (int)maze[0].size() && maze[sr][sc+1] == '.')
{
sc++;
if (escapeMaze()) return true;
sc--;
}
if (sc > 0 && maze[sr][sc-1] == '.')
{
sc--;
if (escapeMaze()) return true;
sc++;
}
if (sr > 0 && maze[sr-1][sc] == '.')
{
sr--;
if (escapeMaze()) return true;
sr++;
}
maze[sr][sc] = '.';
grids++; Tsec++;
return false;
}
int main()
{
while (scanf("%d %d %d", &n, &m, &Tsec) && n)
{
grids = n * m - 1;
maze.clear(); maze.resize(n);
for (int i = 0; i < n; i++)
{
cin>>maze[i];
for (int j = 0; j < m; j++)
{
if (maze[i][j] == 'S') sr = i, sc = j; //别忘记了这里是'S'
else if (maze[i][j] == 'D') dr = i, dc = j, maze[i][j] = '.';
else if (maze[i][j] == 'X') grids--;
}
}
int t = Tsec - (abs(dr - sr) + abs(dc-sc));
if (t < 0 || (t & 1) || grids < Tsec) puts("NO");
else if (escapeMaze()) puts("YES");
else puts("NO");
}
return 0;
}
HDU 1010 Tempter of the Bone heuristic 剪枝法,布布扣,bubuko.com
HDU 1010 Tempter of the Bone heuristic 剪枝法
原文：http://blog.csdn.net/kenden23/article/details/32343857