DFS--奇偶剪枝

本文主要是介绍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 但是要求时间是偶数的，都可以直接判断不可达！

比如有一地图：

[c-sharp]  view plain copy  
 S...  
 ....  
 ....  
 ....  
 ...D  

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

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

[c-sharp]  view plain copy  
 S..X  
 XX.X  
 ...X  
 .XXX  
 ...D  

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

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

例题：ZOJ Problem Set - 2110 Tempter of the Bone

题目意思是讲有一只狗要吃骨头，结果进入了一个迷宫陷阱，迷宫里每走过一个地板费时一秒，该地板就会在下一秒塌陷，所以你不能在该地板上逗留。迷宫里面有一个门，只能在特定的某一秒才能打开，让狗逃出去。现在题目告诉你迷宫的大小和门打开的时间，问你狗可不可以逃出去，可以就输出YES,否则NO。

搜索时要用到的剪枝：

1.如果当前时间即步数(step) >= T 而且还没有找到D点，则剪掉。

2.设当前位置(x, y)到D点(dx, dy)的最短距离为s，到达当前位置(x, y)已经花费时间(步数)step，那么，如果题目要求的时间T - step < s，则剪掉。

3. 对于当前位置(x, y)，如果，(T-step-s)是奇数，则剪掉(奇偶剪枝)。

4.如果地图中，可走的点的数目(xnum) < 要求的时间T，则剪掉(路径剪枝)。

[cpp]  view plain copy  
 // =====================================================================================  
 //   
 //       Filename:  zoj2110.cpp  
 //    Description:  Tempter of the Bone  
 //      Algorithm:  DFS   
 //         Status:  RunTime:90ms    RunMemory:188KB   
 //        Version:  1.0  
 //        Created:  2011年02月01日 14时26分10秒   
 //       Revision:  none  
 //       Compiler:  g++  
 //         Author:  Moose Chan, chyshnu@gmail.com  
 //        Company:  SHNU  
 //  
 // =====================================================================================  
 #include <iostream>  
 #include <cmath>  
 using namespace std;  
 int N, M, T, sx, sy, ex, ey;  
 char map[6][6];  
 const int dir[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };  
 bool solved =  false, arrd[6][6];  
 int Distance ( int x, int y )   
 {  
     return abs ( (double)x - ex ) + abs ( (double)y - ey ); // 当前点(x,y)到终点(ex,ey)的最短距离  
 }  
 void DFS ( int x, int y, int step )  
 {  
     if ( solved ) return;  
     if ( map[x][y] == 'D' && step == T ) {  
         solved = true;  
         return;  
     }  
     if ( step >= T ) return;                    // 当前时间即步数(step) >= T 而且还没有找到D点  
     int dis = T - step - Distance ( x, y );  
     if ( dis < 0 || dis % 2 ) return;           // 剩余步数小于最短距离或者满足奇偶剪枝条件  
     for ( int i = 0; i < 4; i += 1 ) {  
         int tx = x + dir[i][0];  
         int ty = y + dir[i][1];  
         int tstep = step + 1;  
         if ( tx >= 0 && tx < N && ty >= 0 && ty < M && map[tx][ty] != 'X' && !arrd[tx][ty]) {  
             arrd[tx][ty] = true;  
             DFS ( tx, ty, tstep );  
             arrd[tx][ty] = false;  
         }  
     }  
 }  
 int main ( int argc, char *argv[] )  
 {  
     while ( cin >> N >> M >> T, N+M+T ) {  
         solved = false;  
         int xnum = 0;                           // 记录'X'的数量  
         for ( int i = 0; i < N; i += 1 ) {  
             cin.get();  
             for ( int j = 0; j < M; j += 1 ) {  
                 cin >> map[i][j];  
                 arrd[i][j] = false;  
                 if ( map[i][j] == 'S' ) {  
                     sx = i;  
                     sy = j;  
                     arrd[i][j] = true;  
                 }  
                 else if ( map[i][j] == 'D' ) {  
                     ex = i;  
                     ey = j;  
                 }  
                 else if ( map[i][j] == 'X' ) {  
                     xnum++;  
                 }  
             }  
         }  
         if ( N * M - xnum > T ) { // 可通行的点必须大于要求的步数，路径剪枝。  
             DFS ( sx, sy, 0 );  
         }  
         if ( solved )  
             cout << "YES" << endl;  
         else   
             cout << "NO" << endl;  
     }  
     return 0;   
 }  
 转自：http://blog.csdn.net/chyshnu/article/details/6171758/