從零開始DFS HDOJ.1342 Lotto [從零開始DFS(0)] — DFS思想與框架/雙重DFS HDOJ.1010 Tempter of the Bone [從零開始DFS(1)] —DFS四向搜索/奇偶剪枝 HDOJ(HDU).1015 Safecracker [從零開始DFS(2)] —DFS四向搜索變種 HDOJ(HDU).1016 PRime Ring Problem (DFS) [從零開始DFS(3)] —小結(jié)：做DFS題目的關(guān)注點 HDOJ(HDU).1035 Robot Motion [從零開始DFS(4)]—DFS題目練習(xí) HDOJ(HDU).1241 Oil Deposits(DFS) [從零開始DFS(5)] —DFS八向搜索/雙重for循環(huán)遍歷 HDOJ(HDU).1258 Sum It Up (DFS) [從零開始DFS(6)] —DFS雙重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [從零開始DFS(７)]—DFS練習(xí)/check函數(shù)的思想
給出一張大小為n * m的地圖，其中： X代表墻壁，走不通； S代表起點； D代表終點； . 代表空白區(qū)域，即可以走通。 求解是否正好可以在第T步的時候走到終點，并且不能走回頭路（即走過的地方不能再走）。
典型的地圖搜索問題嘛，首先想到的就是DFS。先回顧一下上次探討的內(nèi)容。 傳送門：
HDOJ.1342 Lotto [從零開始DFS(0)]
1.幾個名詞 DFS的搜索原則 遞歸 剪枝 遞歸邊界
2.DFS的函數(shù)模型
void dfs( 參數(shù) ){ // 遞歸邊界 // 可以是檢查是否滿足解的要求 // 完成某系列動作 // 繼續(xù)遞歸調(diào)用dfs}3.其實上次有2個問題沒有討論的太明白
（1） Q：沒有進(jìn)行排序，為什么自動是字典序？
A:因為題目給的數(shù)據(jù)，即數(shù)組a本來就是按照升序排好的，按照上次說的搜索原則，搜索到的解，一定是按照遞增排列好的。每次遞歸調(diào)用dfs的時候，都是先假定選取這個數(shù)字，然后再看不選這個數(shù)字的情況，那么選取的這個數(shù)字，肯定比不選這個數(shù)字以后的情況來的小，所以他的下一個解，一定比這個解的字典序要大。如：
| 位置 | 1 | 2 | …… |
|---|---|---|---|
| a數(shù)組 | 1 | 2 | …… |
| b數(shù)組 | 1 | 待定 | …… |
若現(xiàn)在b的第二個位置選了2
| 位置 | 1 | 2 | …… |
|---|---|---|---|
| a數(shù)組 | 1 | 2 | …… |
| b數(shù)組 | 1 | 2 | …… |
那么這組解就是12XXXX
若不選2呢？
| 位置 | 1 | 2 | …… |
|---|---|---|---|
| a數(shù)組 | 1 | 2 | …… |
| b數(shù)組 | 1 | 待定（3、4等都有可能） | …… |
那么這組解就有可能是： 13XXXX 或者 14XXXX 自然字典序就比上面的情況來的大。
（2） Q： 在遞歸調(diào)用的時候，如何判斷這個節(jié)點（或者數(shù)組的某個元素）已經(jīng)訪問過了呢？
A：因為上次的題是一維數(shù)組并且按順序訪問的，就不用檢查是否訪問過了。但是這個題就需要檢查了，一般采用的是visit數(shù)組。
先上代碼，掰開了揉碎了慢慢來。。
首先是main函數(shù)
while(scanf("%d%d%d",&n,&m,&t) &&(n+m+t)){ memset(mp,0,sizeof(mp)); memset(visit,0,sizeof(visit)); for(int i = 0;i<n;++i) scanf("%s",mp[i]); init(); judge = false; dfs(x1,y1,0); if(judge) printf("YES/n"); else printf("NO/n"); }按照題意讀取nmt三個數(shù)據(jù)，并且初始化地圖數(shù)組mp和檢查是否訪問過的數(shù)組visist，之后讀入地圖的數(shù)據(jù)，接著是init函數(shù)，看看init做了什么。
void init(){ for(int i = 0;i<n;++i){ for(int j = 0;j<m ;++j){ if(mp[i][j] == 'S') {x1 = i;y1 = j;} else if(mp[i][j] == 'D') {x2 = i;y2 = j;} else if(mp[i][j] == 'X') visit[i][j] = true; } }}原來是找到起點S和終點D的位置，并且把墻所在坐標(biāo)的visit寫為true，代表訪問過。不難理解，既然走不通，就把它變成訪問過，只要在dfs過程中稍加判斷也不會再次訪問了。
回到main函數(shù)，接著是吧judge改為false，這個是遞歸邊界。題目只要求找出能還是不能，如果我搜索到某一情況，判定可以走到終點，那么明顯就沒有必要繼續(xù)搜索下去了。接下來是重頭戲，dfs函數(shù)。
void dfs(int x, int y, int s){ if(check(x, y) == false)return;//判斷是否出界 visit[x][y] = true;//改變當(dāng)前節(jié)點為訪問過 if(x==x2 && y == y2 && s == t){//判斷是否滿足題目要求的解 judge = true; return; } if(((t-s)%2 != (abs(x-x2) + abs(y-y2)) %2)) return;//奇偶剪枝 if(t-s-abs(x-x2)-abs(y-y2)<0) return;//步數(shù)不夠剪枝 for(int i = 0;i<4;++i){//遞歸調(diào)用dfs if(!visit[x+spx[i]][y+spy[i]]&&!judge){ dfs(x+spx[i],y+spy[i],s+1); visit[x+spx[i]][y+spy[i]] = false; } }}首先dfs有3個形式參數(shù)，xy代表入口坐標(biāo)，即搜索入口，s代表走的步數(shù)。首先按照check函數(shù)，檢查當(dāng)前坐標(biāo)是否超出地圖邊界，若超出，則終止遞歸。
check函數(shù)：
bool check(int x, int y){ if(x<0||x>=n||y<0||y>=m) return false; else return true;}接著把當(dāng)前的位置，變?yōu)樵L問過。緊接著就是判斷當(dāng)前坐標(biāo)是否就是終點坐標(biāo)并且看步數(shù)是否可題目要求的一致，若是的話，judge變?yōu)閠rue表示找到解了，以后遞歸都沒必要做了。 然后是奇偶剪枝。
（圖2-1）
Tip:只能上下左右走，不能斜著走。
如圖2-1所示，由start到end圖中最短路徑為紅色，走了12步。相比于紅色路徑，藍(lán)色路徑大費周折，大家可以數(shù)一下，共走了14步。此時步數(shù)的偏移量為14-12=2。奇偶剪枝，就是步數(shù)的偏移量永遠(yuǎn)為偶數(shù)（可證明），因此可以得出：最短路徑步數(shù)+某一偶數(shù)（即偏移量）=某一可行解歩數(shù)。（下面這句是重點）即最短路歩數(shù)和某一可行解歩數(shù)的奇偶性相同。
回到題目，若已知最短路徑歩數(shù)為偶數(shù)，且在某一情況下剩余的步數(shù)為奇數(shù)，那么無論如何也是無法恰好到達(dá)終點的，因此這種情況就不用算啦，終止遞歸。當(dāng)然步數(shù)不夠，也是走不到終點的。
接著遞歸調(diào)用dfs，這里有新東西啦，visit[x+spx[i]][y+spy[i]]是什么鬼。
看一下開頭定義的的：
int spx[] = {1,0,-1,0};int spy[] = {0,1,0,-1};不難發(fā)現(xiàn)，spx為0時spy為±1，反之成立。也可以想到，x±1和y±1分別對應(yīng)的就是地圖上，上下左右移動一個單位。這里是個小trick，用這樣一個的數(shù)組來實現(xiàn)上下左右的移動，畢竟一個for循環(huán)多好寫。 當(dāng)且僅當(dāng)下一個位置沒有訪問過，并且這個時候還沒有找到可行解時，遞歸調(diào)用dfs，在調(diào)用結(jié)束后，記得要把visit[x+spx[i]][y+spy[i]]置為false。原因很簡單，不能影響到下一次循環(huán)呀：對于下一次循環(huán)[x+spx[i]][y+spy[i]]這個位置，可是沒有訪問過的。（無后效性？？請各位指點）。 這樣一道題，就ac了。
多做題，加緊訓(xùn)練吧！
新聞熱點
疑難解答
