HDU 1010 Tempter of the Bone

题意：从开始位置走到结束位置，恰好走 t 步 YES

否则 NO

搜索题，由于是恰好走到，所以用到了奇偶剪枝

什么是奇偶剪枝，我也是刚知道

所给步数为 t ，起始位置坐标 (begin_x,begin_y), 结束位置坐标 (end_x,end_y)

两位置最短距离为 ju = abs(end_x - begin_x) + abs(end_y - begin_y)

若 t - ju 为奇数，则无论如何不能恰好走到

为偶数才有可能恰好走到

代码中 pos + dis 即 ju

代码如下：

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<iostream>

using namespace std;

int m,n,t;

char map[][];

int vis[][];

int flag;

int begin_x,begin_y,end_x,end_y;

int p[][] = {{-,},{,},{,},{,-}};  //偏移量：上，下，左，右

void dfs(int x,int y,int pos)             //pos 为当前已走步数

{

    if(flag) return ;                  //剪枝：已经到达目的地

    if(pos > t) return ;               //剪枝：步数超过 t

    if(x == end_x && y == end_y && pos == t)  //恰好 t 步走到

    {

        flag = ;

        return ;

    }

    int dis = abs(end_x - x) + abs(end_y - y);  //当前位置到结束位置的最短距离

    if((t - dis - pos) %  != ) return;       //奇偶剪枝，很重要，不剪TLE

    for(int i = ; i < ; i ++)         //搜索四个方向

    {

        int tx = x + p[i][];

        int ty = y + p[i][];

        if(tx >=  && tx < m && ty >=  && ty < n && !vis[tx][ty] && map[tx][ty] != 'X')

        {

            vis[tx][ty] = ;

            dfs(tx,ty,pos + );

            vis[tx][ty] = ;

        }

    }

}

int main()

{

    while(~scanf("%d%d%d",&m,&n,&t) && (m || n || t))

    {

        memset(vis,,sizeof(vis));

        flag = ;

        int k = ;

        for(int i = ; i < m; i ++)

        {

            for(int j =  ; j < n; j++)

            {

                cin>>map[i][j];             //scanf注意回车

                if(map[i][j] == 'S')

                {

                    begin_x = i;

                    begin_y = j;

                    vis[i][j] = ;

                }

                if(map[i][j] == 'D')

                {

                    end_x = i;

                    end_y = j;

                }

                if(map[i][j] == 'X')

                    k ++;

            }

        }

        if((m * n - k) > t) dfs(begin_x,begin_y,);

        if(flag) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}