HDUOJ 1010 Tempter of the Bone 解题报告

    题目的意思是给定一个起点、一个出口、还有一些墙。给定一个时间T，要求刚好在T秒的时候走到出口处。     刚开始我用的BFS，结果后来才发现把题看错了。仔细一看：给定一个时间T，要求刚好在T秒的时候走到出口处。  所以说广度搜索应该是不可行了，因为不是要求在T秒之内到达。

    之后改用DFS，超时。所以需要剪枝。剪掉一些不可能的情况，比如剩余的时间和剩余的步数奇偶性不同，则不可能到达，所以要剪掉。另外可以走的方块的数量（这里可以走的指的是除去墙以外的所有地方，包括起点）小于等于T ，也是不可能的，因为一个地方只能走一次。这里又可以剪掉。
AC代码如下：

#include <iostream>
#include <cmath>
using namespace std;
char Map[8][8] = {{0}};
int m, n, t, sx, sy, dx, dy, wall, escape;
int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

void dfs(int x, int y, int cur_t);

int main()
{
    while(cin >> n >> m >> t)
    {
        wall = 0;
        if(0 == n && 0 == m && 0 == t)
            break;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= m; ++j)
            {
                cin >> Map[i][j];
                if('S' == Map[i][j]) {sx = i; sy = j; Map[i][j] = 'X';} //将起点标记为墙，这里注意起点S不计入到wall变量中
                else if('D' == Map[i][j]) {dx = i; dy = j;}
                else if('X' == Map[i][j]) wall++; //计算墙的数量，不包括起点
            }
        }

        if(n * m - wall <= t) //需要走t步， 如果可以走的地方少于等于t，则不可能到达
        {
            cout << "NO\n";
            continue;
        }
        escape = 0;
        dfs(sx, sy, 0);
        if(escape)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

void dfs(int x, int y, int cur_t)
{
    if(x <= 0 || x > n || y <= 0 || y > m)
        return;
    if(x == dx && y == dy && cur_t == t)
    {
        escape = 1;
        return;
    }
    int p = t - cur_t - abs(dx - x) - abs(dy - y);   //p为奇数就是不可能的，画画图就知道为什么这样写了。
    if(p < 0 || p&1) return;                //判断奇数可以直接将一个数与上1。
    for(int i = 0; i < 4; ++i)
    {
        if('X' != Map[x + dir[i][0]][y + dir[i][1]])
        {
            Map[x + dir[i][0]][y + dir[i][1]] = 'X';
            dfs(x + dir[i][0], y + dir[i][1], cur_t + 1);
            if(escape) return;
            Map[x + dir[i][0]][y + dir[i][1]] = '.';
        }
    }
    return;
}