HDU 1010 Tempter of the Bone( DFS + 奇偶剪枝 )

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1010

题目大意是有一只狗在古代的一个迷宫发现了一块肉骨头，然后发现是个陷阱，迷宫会在 T 秒后坍塌，问小狗能不能逃出迷宫。迷宫大小为n*m，然后小狗每踩过一个地方，那个地方就会坍塌，就不能再走了，然后会给出门的位置。

一开始直接非常冲动地用了BFS，结果WA得很有节奏，后来认真看了题目，原来是DFS，不过后来想了想，BFS也是可以做的。但是简单的DFS还是解决不了问题的，这里还要进行奇偶剪枝，一种挺常见的剪枝吧，百度一下立马就能查到了。

最后还是WA了好几次，研究了好久突然发现，我把起点看成是可以走的，也就是 ‘.’ ,然后判断可不可走的时候用了 ！= ‘X’，结果门所在的位置也算进去了，后来改成 == ‘.’终于过了，以后对于这种小细节还是得多考虑考虑。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN = 7 + 5;

int sx, sy;
int ex, ey;
int n, m, t;
int escaped;
char maze[MAXN][MAXN];
int dir_x[4] = { 0, 0, -1, 1 };
int dir_y[4] = { -1, 1, 0, 0 };

void DFS(int x, int y, int tt)
{
    //已经逃出
    if(escaped == 1)
        return;

    //奇偶剪枝
    if((tt < abs(ex - x) + abs(ey - y)) || ((tt - abs(ex - x) - abs(ey - y)) & 1))
        return;
    else if(tt == 0)
    {
        if(x == ex && y == ey)
        {
            escaped = 1;
            return;
        }
        else
            return;
    }
    else
        for(int i = 0; i < 4; ++i)
        {
            int xx = x + dir_x[i];
            int yy = y + dir_y[i];

            //边界判断和是否可走
            if(xx >= 0 && xx < n && yy >= 0 && yy < m && maze[xx][yy] == '.')
            {
                maze[xx][yy] = 'X';
                DFS(xx, yy, tt - 1);

                //还原，为下次DFS作准备
                maze[xx][yy] = '.';
            }
        }
}

int main()
{
    while(scanf("%d%d%d", &n, &m, &t) == 3 && (n || m || t))
    {
        char str[MAXN];

        for(int i = 0; i < n; ++ i)
        {
            scanf("%s", str);

            for(int j = 0; j < m; ++ j)
            {
                maze[i][j] = str[j];

                if(maze[i][j] == 'S')
                {
                    sx = i;
                    sy = j;
                }
                else if(maze[i][j] == 'D')
                {
                    ex = i;
                    ey = j;
                    maze[i][j] = '.';
                }
            }
        }

        escaped = 0;
        DFS(sx, sy, t);

        if(escaped)
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}