学步园

HDOJ 1010解题 ：

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

在回顾搜索算法，DFS、BFS、回溯等。以HDOJ 1010题练习，虽然题目非常简单，但还是花了较长时间才AC。一开始没有剪枝，果断超时。进行了奇偶剪枝后ac。

//奇偶剪枝：如果起点横纵坐标和与终点坐标和奇偶性不同，则说明要走奇数步，如果要求走t步，
    //t为偶数，则肯定不可能有答案；反之亦然。

#include <iostream>
#include <cstdlib>

using namespace std;
int n,m,t;
char map[8][8];
int visited[8][8];
int stepx[] = {-1, 0, 1, 0};
int stepy[] = {0, 1, 0, -1};
int start[2];
int end[2];
int depth;
int escape;
void DFS(int x, int y, int time)
{
    if(x<=0 || x>n || y<=0 || y>m)//防止越界
    {
        return;
    }
    visited[x][y]=1;
    depth++;
    if(map[x][y]=='D' && depth == time)
    {
        escape = true;
        return;
    }
    //奇偶剪枝：如果起点横纵坐标和与终点坐标和奇偶性不同，则说明要走奇数步，如果要求走t步，
    //t为偶数，则肯定不可能有答案；反之亦然。
    int temp=t-abs(start[0]-end[0])-abs(start[1]-end[1]);
    if(temp<0 || temp&1)
        return;
    for(int i=0 ; i<4 ; ++i)
    {
        if(visited[x+stepx[i]][y+stepy[i]] == 0 && !escape)
        {
            DFS(x+stepx[i], y+stepy[i],time);
        }
        else if(escape)
        {
            return;
        }
    }
   depth--;
   visited[x][y] = 0;
}
int main()
{
    while((cin >> n >> m >> t) && (n || m || t))
    {
        escape = false;
        depth = -1;
        for(int i=0;i<=n;++i)
        {
            for(int j=0;j<=m;++j)
                visited[i][j] = 1;

        }
        for(int i=1 ; i<=n ; ++i)
        {
            for(int j=1 ; j<=m ; ++j)
            {
                cin >> map[i][j];
                if(map[i][j] == 'S')
                {
                    start[0] = i;
                    start[1] = j;
                }
                if(map[i][j] == 'D')
                {
                    end[0] = i;
                    end[1] = j;
                }
                if(map[i][j] != 'X')
                {
                    visited[i][j] = 0;
                }
            }
        }
        DFS(start[0],start[1],t);
        if(escape)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    return 0;
}