DFS---奇偶剪枝

奇偶剪枝技巧原链接

什么是剪枝？把不可行的一些情况剪掉，例如走迷宫时运用回溯法，遇到死胡同时回溯，造成程序运行时间长。剪枝的概念，其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义，就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。

什么是奇偶剪枝？

把矩阵看成如下形式： 
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 必然是奇数步，从 0 走向 0 必然是偶数步。

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

比如一张地图

S...  
....  
....  
....  
...D 

 

要求从S点到达D点，此时，从S到D的最短距离为s = abs ( dx - sx ) + abs ( dy - sy )。

如果地图中出现了不能经过的障碍物：

S..X  
XX.X  
...X  
.XXX  
...D 

 

此时的最短距离s' = s + 4，为了绕开障碍，不管偏移几个点，偏移的距离都是最短距离s加上一个偶数距离。

就如同上面说的矩阵，要求你从0走到0，无论你怎么绕，永远都是最短距离(偶数步)加上某个偶数步；要求你从1走到0，永远只能是最短距离(奇数步)加上某个偶数步。

HDU1010

题意：

给定你起点S，和终点D，问你是否能在 T 时刻恰好到达终点D。

思路：

DFS+剪枝

AC代码：

/**
DFS的奇偶剪枝
已知起点和终点，是否能在t时刻恰好到达
*/
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
char a[15][15];//地图
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,t;
int sx,sy,ex,ey;//起始终止位置
bool flag;
void dfs(int x,int y,int nowt)
{
    if(nowt==t&&x==ex&&y==ey)
    {
        flag=true;
        return;
    }
    int k=(t-nowt)-(abs(x-ex)+abs(y-ey));/**当前点到终点的最短路*/
    if(k<0||k&1)/**k<0或者为奇数则不可能到达*/
    {
        return ;//奇偶剪枝
    }
    for(int i=0;i<4;i++)
     {
         int nx=x+dx[i];
         int ny=y+dy[i];
         if(a[nx][ny]!='X'&&nx>=1&&nx<=n&&ny>=1&&ny<=m)
         {
             a[nx][ny]='X';//不能停留在某一个格子
             dfs(nx,ny,nowt+1);
             if(flag)
                return;
             a[nx][ny]='.';
         }
     }
     return;
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&t)!=EOF)
    {
        getchar();
        if(n==0&&m==0&&t==0)
            break;
        int w=0;//记录墙(X不能走的点)的数量来剪枝
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%c",&a[i][j]);
                if(a[i][j]=='S')//起始位置
                {
                    sx=i,sy=j;
                }
                else if(a[i][j]=='D')//终点
                {
                    ex=i,ey=j;
                }
                else if(a[i][j]=='X')
                {
                    w++;
                }
            }
            getchar();

        }
        if((n*m-w)<=t)
        {
            cout<<"NO"<<endl;
        }
        else
        {
            flag=false;
            a[sx][sy]='X';
            dfs(sx,sy,0);
            if(flag==true)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
    }
}