Hdu 1010 Tempter of the Bone (DFS 经典奇偶剪枝)

╰半橙微兮° 2022-09-20 12:55 185阅读 0赞

题意：一个n\*m的迷宫，需要在迷宫中生存的时间为t。S为起点，D为终点。每个格子只能踩一次，且只能维持一秒，然后该块地板就会塌陷，所以你必须每秒走一步。问是否可以到D点时，所用时间恰好为T。

典型的迷宫搜索题，很经典的DFS奇偶剪枝。突然发现abs()竟然不在头文件math.h下， 而是在stdlib.h下。

以下分析参考了湖南工业大学的PPT《07\_ACM\_DFS+BFS》。

剪枝一：可走的block的总数小于时间。

剪枝二：

可以把map看成这样：

0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

从为 0 的格子走一步，必然走向为 1 的格子

从为 1 的格子走一步，必然走向为 0 的格子

即：  
0 ->1或1->0 必然是奇数步  
0->0 走1->1 必然是偶数步

所以当遇到从 0 走向 0 但是要求时间是奇数的，或者， 从 1 走向 0 但是要求时间是偶数的 都可以直接判断不可达！

那么设所在位置 (x,y) 与 目标位置 (dx,dy)

如果abs(dx-x)+abs(dy-y) 为偶数，则说明 abs(dx-x)和 abs(dy-y)的奇偶性相同，需要走偶数步

如果abs(dx-x)+abs(dy-y)为奇数，那么说明 abs(dx-x)和 abs(dy-y)的奇偶性不同，需要走奇数步

(ti-setp)表示剩下还需要走的步数，由于题目要求要在 ti时 恰好到达，那么 (ti-step)与 abs(x-y)+abs(dx-dy) 的奇偶性必须相同

因此 temp=ti-step-abs(dx-x)-abs(dy-y) 必然为偶数！

//96ms
    #include <cstdio>
    #include <cstdlib>
    
    char g[10][10];
    int n,m,t,dx,dy;
    bool flag;
    int dirx[4]={0,0,1,-1};
    int diry[4]={-1,1,0,0};
    
    bool OK (int x,int y)
    {
        return x>=0 && x<n && y>=0 && y<m && g[x][y]!='X';
    }
    
    void DFS (int u,int v,int step)
    {
        if (u==dx && v==dy && step==t) flag=true;
        if (step>t) return;
        if (flag) return; //已经找到
        if ((t-step)%2!=(abs(dx-u)+abs(dy-v))%2)return; //奇偶性不同
        for (int i=0;i<4;i++)
        {
            int x=u+dirx[i];
            int y=v+diry[i];
            if (OK(x,y))
            {
                g[x][y]='X';
                DFS(x,y,step+1);
                g[x][y]='.';
            }
        }
    }
    
    int main ()
    {
        while (scanf("%d%d%d",&n,&m,&t),n||m||t)
        {
            int sx,sy,cnt=0;
            for (int i=0;i<n;i++)
            {
                scanf("%s",g[i]);
                for (int j=0;j<m;j++)
                    if (g[i][j]=='S')
                    {
                        sx=i;
                        sy=j;
                        g[i][j]='X';
                    }
                    else if (g[i][j]=='D')
                    {
                        dx=i;
                        dy=j;
                        cnt++;
                    }
                    else if (g[i][j]=='.')
                        cnt++;
            }
            if (cnt<t)
            {//可移动的空间不足
                printf("NO\n");
                continue;
            }
            flag=false;
            DFS(sx,sy,0);
            if (flag)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }