http://acm.hdu.edu.cn/showproblem.php?pid=1010?? //題目鏈接

http://ycool.com/post/ymsvd2s//一個(gè)很好理解剪枝思想的博客

http://blog.csdn.net/chyshnu/article/details/6171758//一個(gè)很好舉例的博客

?

Problem Description The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.

The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him. Input The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:

'X': a block of wall, which the doggie cannot enter;?
'S': the start point of the doggie;?
'D': the Door; or
'.': an empty block.

The input is terminated with three 0's. This test case is not to be processed.
Output For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise. Sample Input 4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0 Sample Output NO YES

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

題目意思是講有一只狗要吃骨頭，結(jié)果進(jìn)入了一個(gè)迷宮陷阱，迷宮里每走過一個(gè)地板費(fèi)時(shí)一秒，該地板 就會(huì)在下一秒塌陷，所以你不能在該地板上逗留。迷宮里面有一個(gè)門，只能在特定的某一秒才能打開，讓狗逃出去?，F(xiàn)在題目告訴你迷宮的大小和門打開的時(shí)間，問你狗可不可以逃出去，可以就輸出YES,否則NO。

?

搜索時(shí)要用到的剪枝：

1.如果當(dāng)前時(shí)間即步數(shù)(step) >= T 而且還沒有找到D點(diǎn)，則剪掉。

2.設(shè)當(dāng)前位置(x, y)到D點(diǎn)(dx, dy)的最短距離為s，到達(dá)當(dāng)前位置(x, y)已經(jīng)花費(fèi)時(shí)間(步數(shù))step，那么，如果題目要求的時(shí)間T - step < s，則剪掉。

3. 對(duì)于當(dāng)前位置(x, y)，如果，(T-step-s)是奇數(shù)，則剪掉(奇偶剪枝)。

4.如果地圖中，可走的點(diǎn)的數(shù)目(xnum) < 要求的時(shí)間T，則剪掉(路徑剪枝)。

題目解析：

通過做這題算是懂剪枝的思想了，要學(xué)奇偶剪枝首先要看懂那個(gè)01矩陣（很好理解），之后就沒什么問題了，

剪完枝后大約100ms就過了，怎么說呢，還是了解思想比較重要。

#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> using namespace std; int n,m,t,tx,ty,flag; char map[8][8]; int v[8][8]; int jx[]= {1,-1,0,0}; int jy[]= {0,0,1,-1}; int Distance ( int x, int y ) {return abs(x - tx )+abs( y - ty ); // 當(dāng)前點(diǎn)(x,y)到終點(diǎn)(tx,ty)的最短距離 } void dfs(int x,int y,int ans) {if(ans>t) return ;if(x==tx&&y==ty&&ans==t){flag=1;return ;}int dis=t-ans-Distance(x,y);if(dis<0||dis%2) return ;//?剩余步數(shù)小于最短距離或者滿足奇偶剪枝條件? for(int i=0; i<4; i++){int xx=x+jx[i];int yy=y+jy[i];if(xx>=0&&xx<n&&yy>=0&&yy<m&&v[xx][yy]==0&&map[xx][yy]!='X'){v[xx][yy]=1;dfs(xx,yy,ans+1);if(flag==1)break;v[xx][yy]=0;}}return ; } int main() {int xx,yy,sum;while(scanf("%d%d%d",&n,&m,&t)!=EOF){flag=sum=0;if(n==0&&m==0&&t==0) break;for(int i=0; i<n; i++){scanf("%*c%s",map[i]);}for(int i=0; i<n; i++){for(int j=0; j<m; j++){v[i][j]=0;if(map[i][j]=='X'){sum++;}else if(map[i][j]=='S'){xx=i;yy=j;v[i][j]=1;}else if(map[i][j]=='D'){tx=i;ty=j;}}}v[xx][yy]=1;if(n*m-sum>t){dfs(xx,yy,0);// 可通行的點(diǎn)必須大于要求的步數(shù)，路徑剪枝。 }if(flag==1) printf("YES\n");else printf("NO\n");}return 0; }

?

什么是奇偶剪枝？

把矩陣看成如下形式：
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 的格子走一步，必然走向?yàn)?1 的格子 。
從為 1 的格子走一步，必然走向?yàn)?0 的格子 。
即：
從 0 走向 1 必然是奇數(shù)步，從 0 走向 0 必然是偶數(shù)步。

所以當(dāng)遇到從 0 走向 0 但是要求時(shí)間是奇數(shù)的或者 從 1 走向 0 但是要求時(shí)間是偶數(shù)的，都可以直接判斷不可達(dá)！

?

比如有一地圖：

[c-sharp] view plaincopy

S...??

....??

....??

....??

...D??

要求從S點(diǎn)到達(dá)D點(diǎn)，此時(shí)，從S到D的最短距離為s = abs ( dx - sx ) + abs ( dy - sy )。

如果地圖中出現(xiàn)了不能經(jīng)過的障礙物：

[c-sharp] view plaincopy

S..X??

XX.X??

...X??

.XXX??

...D??

此時(shí)的最短距離s' = s + 4，為了繞開障礙，不管偏移幾個(gè)點(diǎn)，偏移的距離都是最短距離s加上一個(gè)偶數(shù)距離。

就如同上面說的矩陣，要求你從0走到0，無論你怎么繞，永遠(yuǎn)都是最短距離(偶數(shù)步)加上某個(gè)偶數(shù)步；要求你從1走到0，永遠(yuǎn)只能是最短距離(奇數(shù)步)加上某個(gè)偶數(shù)步。

?

關(guān)于奇偶剪枝

首先舉個(gè)例子，有如下4*4的迷宮，'.'為可走路段，'X'為障礙不可通過

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

從S到D的最短距離為兩點(diǎn)橫坐標(biāo)差的絕對(duì)值+兩點(diǎn)縱坐標(biāo)差的絕對(duì)值 = abs(Sx - Dx) + abs(Sy - Dy) = 6，這個(gè)應(yīng)該是顯而易見的。

遇到有障礙的時(shí)候呢

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

你會(huì)發(fā)現(xiàn)不管你怎么繞路，最后從S到達(dá)D的距離都是最短距離+一個(gè)偶數(shù)，這個(gè)是可以證明的

而我們知道：

奇數(shù) + 偶數(shù) = 奇數(shù)
偶數(shù) + 偶數(shù) = 偶數(shù)

因此不管有多少障礙，不管繞多少路，只要能到達(dá)目的地，走過的距離必然是跟最短距離的奇偶性是一致的。

所以如果我們知道從S到D的最短距離為奇數(shù)，那么當(dāng)且僅當(dāng)給定的步數(shù)T為奇數(shù)時(shí)，才有可能走到。如果給定的T的奇偶性與最短距離的奇偶性不一致，那么我們就可以直接判定這條路線永遠(yuǎn)不可達(dá)了。

轉(zhuǎn)載于:https://www.cnblogs.com/zhangmingcheng/p/3984852.html

總結(jié)

以上是生活随笔為你收集整理的HDU1010:Tempter of the Bone(dfs+剪枝)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。