【奇偶剪枝】【HDU1010】Tempter of the Bone

题意：输入一个n*m的迷宫，和一个T：可以在迷宫中生存的最大时间。S为起点，D为终点。并且，每个格子只能踩一次，且只能维持一秒，然后该块地板就会塌陷。所以你必须每秒走一步，且到D点时，所用时间为T。

TIPS：可以在中途某个点就能通过x+y的奇偶性与剩余时间的奇偶性判定能否到D ，达到剪枝的目的。

代码如下

#include <cstdio>

#include <cstring>

#include <iostream>

#include <stdlib.h>

using namespace std;

char map[9][9];

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

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

int n,m,t,sum;

int sx,sy,ddx,ddy;

bool dfs(int x,int y,int time)

{

    int px,py;

    if(x==ddx && y==ddy && time==t)

    {

        return true;

    }

    else

    {

        if(abs(ddx-x)+abs(ddy-y)>t-time)return false;

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

        {

            px=x+dx[i];

            py=y+dy[i];

            if(map[px][py]!='X' && time+1<=t)

            {

                map[px][py]='X';

                if(dfs(px,py,time+1))return true;

                map[px][py]='.';

            }

        }

    }

    return false;

}

int main()

{

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

    {

        memset(map,'X',sizeof(map));

        sum=0;

        getchar();

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

        {

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

            {

                scanf("%c",&map[i][j]);

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

                {

                    sx=i;

                    sy=j;

                }

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

                {

                    ddx=i;

                    ddy=j;

                }

                if(map[i][j]=='.')sum++;

            }

            getchar();

        }

        if(sum+1<t || (t+sx+sy+ddx+ddy)%2==1)printf("NO\n");

        else

        {

            map[sx][sy]='X';

            if(dfs(sx,sy,0))printf("YES\n");

            else printf("NO\n");

        }

    }

    return 0;

}

巴特西

【奇偶剪枝】【HDU1010】Tempter of the Bone

最新文章

热门文章