hdu1010-Tempter of the Bone-（dfs+奇偶剪枝）

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

翻译：有只狗被困了，S是起点，D是门，W是墙不能走，‘ . ’是可以走的路，走一次就会在1秒内坍塌，也就是不能停留也不能走回头路，门只在第T秒打开，问是否能逃命？

解题：一开始以为是三维bfs，但是地图上的时间维度是错误的，因为走过一次地面坍塌，只能有一个时间维度。百度找了居然一个bfs都没有，不得不用dfs，无限超时，甚至记忆化搜索也超时。见识到了高端的剪枝。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<math.h>

#include<string>

#include<map>

#include<queue>

#include<stack>

#include<set>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

bool vis[][];

char a[][];

int d[][]={ {-,}, {,}, {,-}, {,} };///上下左右

int n,m,T,cnt;

bool flag;

struct node

{

    int x;

    int y;

    int t;

};

node door,start;

void dfs(int x,int y,int t)///当前用了多少时间

{

    if( x==door.x && y==door.y && t==door.t )

    {

        flag=true;

        return ;

    }

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

    {

        int cha=T-t-abs(door.x-x)-abs(door.y-y);///核心代码

        int xx=x+d[i][];

        int yy=y+d[i][];

        int tt=t+;

        if( !flag && xx>= && xx<n && yy>= && yy<m && !vis[xx][yy] && (a[xx][yy]=='.'||a[xx][yy]=='D') && cha>= && cha%== )

        {

            vis[xx][yy]=true;

            dfs(xx,yy,tt);

            vis[xx][yy]=false;

        }

    }

}

int main()///HDU1010

{

    while(scanf("%d%d%d",&n,&m,&T) && (n+m+T) )

    {

        memset(a,,sizeof(a));

        memset(vis,false,sizeof(vis));

        flag=false;

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

            scanf("%s",a[i]);

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

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

        {

            if( a[i][j]=='D' )///终点

                door.x=i,door.y=j,door.t=T;

            if( a[i][j]=='S' )///起点

            {

                start.x=i,start.y=j,start.t=;

                vis[ start.x ][ start.y ] = true;

            }

        }

        dfs( start.x,start.y, );

        if(flag)

            printf("YES\n");

        else

            printf("NO\n");

    }

    return ;

}

dfs内，x和y表示当前坐标，t表示当前花了多少时间。

当前步数到终点的最短距离：abs(door.x-x)+abs(door.y-y)

还需要花的时间：T-t

走最短路的话还剩余的时间：cha = T - t - abs(door.x-x) + abs(door.y-y)

在没有障碍的情况下，cha至少要等于0，如果有障碍，cha要大于0，剪枝剪掉那些就算没障碍走最短路也走不到的情况。

奇偶剪枝：

举例：

0 1 0 1

0 0

0 1 1

1 0 1 0

假设红色1要走到蓝色1，最短只需要走2步，但是现在有4步，必须绕远，绕过粉色1和粉色0走到蓝色1，如果是3步，怎么走都走不到。

巴特西

hdu1010-Tempter of the Bone-（dfs+奇偶剪枝）

最新文章

热门文章