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