HDU 1010 Tempter of the Bone (ZOJ 2110) DFS+剪枝

传送门：

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

ZOJ:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1110

题目大意:

一只狗陷入了迷宫，他每秒必须走一步，并且不能重复走已经走过的地方，给定一个出口，要求在恰好为T的时间到达，如果可以，输出YES否则NO

不断的TLE，然后搜了下题解。

这题最漂亮的剪枝就在于奇偶的判断上。Orz

DFS过程中，设终点的坐标为door_x,door_y。当前的坐标为x,y，目标时间为target,当前时间为step

那么如果他能敲好在target-step的时间到达，那么 target - step 和 abs(door_x - x) + abs(door_y - y) 奇偶性相同。

即（ target - step ） % 2== （ abs(door_x - x) + abs(door_y - y) ） % 2

根据奇-奇=偶，偶-偶=偶，可以直接写成

remain=target- (step + abs(door_x - x) + abs(door_y - y))

remain & 1 （为1的话说明remain最后一位为1，显然奇偶性不同）

其他两个剪枝看代码吧

#include<cstdio>

#include<queue>

#include<cmath>

using namespace std;

const int MAXN=10;

char maze[MAXN][MAXN];

const int dx[]={1 ,-1, 0 , 0};

const int dy[]={0 , 0 ,1 ,-1};

int start_x,start_y,door_x,door_y;

bool dfs(int x,int y,int step,int target)

{

    if(step>target)              //剪枝1

        return false;

    int remain=target- (step + abs(door_x - x) + abs(door_y - y));//当前和终点的距离

    if(remain < 0 || remain & 1 ) //剪枝2，如果当前距离更大那么答案显然不存在

        return false;			//如果奇偶性不同也不行,奇-奇=偶，偶-偶=偶

								//Orz想出来的人

    for(int i=0;i<4;i++)

    {

        int nx=x + dx[i];

        int ny=y + dy[i];

        if(maze[nx][ny]=='.')

        {

            maze[nx][ny]='X';

            if(dfs(nx,ny,step+1,target))

                return true;

            maze[nx][ny]='.';

        }

        else if(maze[nx][ny]=='D' && step+1==target)

            return true;

    }

    return false;

}

int main()

{

    int n,m,t;

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

    {

		int empty=0;

        for(int i=1;i<=n;i++)

        {

			scanf("%s",maze[i]+1); //一开始WA不断就是因为输入

            for(int j=1;j<=m;j++)

            {

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

                    start_x=i,start_y=j;

                else if(maze[i][j]=='D')

                    door_x=i,door_y=j;

				if(maze[i][j]=='.')

					empty++;

            }

        }

		if(empty +1 < t)       //剪枝3，如果可走的少于出现出口的时间，显然无解。

        {

                printf("NO\n");

                continue;

        }        

        for(int i=0;i<=n+1;i++)			//最外层直接包上X，省了等下判断越界问题。

            maze[i][0]=maze[i][m+1]='X';

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

            maze[0][i]=maze[n+1][i]='X';

        printf("%s\n",dfs(start_x,start_y,0,t)==true? "YES":"NO");

    }

}

巴特西

HDU 1010 Tempter of the Bone (ZOJ 2110) DFS+剪枝

最新文章

热门文章