HDU-1010-Tempter of the Bone

这题的题意说的是，一个小狗贪吃中了陷阱的故事，问小狗是否能在T时刻到达出口位置。
这题的话，因为不是寻求最短路嘛，所以我们用dfs，我们搜索之前可以得到一个式子，就是如果空白块要少于我们要走的步数的话，那我们就永远也走不到。
因为题目中说的是，我们不能回头，而且一个砖块只能停留一秒，所以我们就要刚刚好到达，所以就有了上面的式子。
这是第一个剪枝，还有另一个剪枝，名叫奇偶性剪枝。
所谓奇偶性剪枝就是，我们可以知道对于曼哈顿距离，也就是最短的当前点到终点的距离是已知的。
我们设原点为S，那就有最短步数minstep，如果minstep加上我们从S走到当前点x的步数t，也就是t+minstep与我们要走的T步之间的差是奇数，我们就走不到。
因为我们无论怎么走我们都要走曼哈顿距离及其以上的路，所以我么无论怎么走，我们都要走这条曼哈顿路，也可能是它的映射，至于其余的步数，都是相互抵消的。
然后我们每次走的时候，因为都是从当前点出发的，所以我们就要用T-t，就是我们还要走的步数，如果它与此时的minstep的差是奇数，我们就不走。
这其实就是从原点推到了其它点，还请读者自行体会。

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int maze[10][10];
int vis[10][10];
int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int N, M, T, sx, sy, ex, ey, wall, flag;

void dfs(int r,int c,int t)
{
    if (r==ey&&c==ex&&t==T) {
        flag=1;
        return;
    }
    if (flag)
        return;
    int minstep = abs(c - ex) + abs(r - ey);
    int odd = T - t - minstep;//t+minstep
    if (odd<0||odd&1)
        return;
    for (int i = 0; i < 4; i++) {
        int row = r + d[i][0];
        int col = c + d[i][1];
        if (row>=0&&row<N&&col>=0&&col<M&&!vis[row][col]&&maze[row][col]) {
            vis[row][col] = 1;
            dfs(row,col,t+1);
            vis[row][col] = 0;
        }
    }
}

int main()
{
    char ch;
    ios::sync_with_stdio(false);
    while (cin>>N>>M>>T&&N+M+T) {
        wall = 0;
        memset(vis, 0, sizeof(vis));
        memset(maze, 0, sizeof(maze));
        for (int i = 0; i < N;i++) {
            for (int j = 0;j<M;j++) {
                cin >> ch;
                if (ch=='.')
                    maze[i][j] = 1;
                else if (ch=='S') {
                    maze[i][j] = 1;
                    sx = j;
                    sy = i;
                }
                else if (ch=='D') {
                    maze[i][j]=1;
                    ex = j;
                    ey = i;
                }
                else
                    wall++;
            }
        }
        if (N*M-wall<T) {
            cout << "NO" << endl;
            continue;
        }
        vis[sy][sx] = 1;
        flag = 0;
        dfs(sy, sx, 0);
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}