深搜與廣搜是搜索算法中最常用的兩種算法，通過深度優先搜索解決問題還會用到回溯和剪枝，讓我們一起進入本章，了解深搜的基本概念和模板，并學會解決一些常見問題。
目錄
問題導入
走迷宮問題
如何走？
問題建模
如何表示迷宮地圖等信息呢？
如何表示每次移動的過程？
走迷宮問題參考程序
深度優先搜索概述
解決問題時的注意事項
訓練：迷宮
參考代碼
訓練：全排列問題
參考代碼
問題導入
走迷宮問題
現在有一個3*3的迷宮，小知在迷宮的左上角，迷宮出口在右下角，請你幫小知算一算，他有多少種方案可以走出迷宮（每個格子不能重復走動）。
迷宮中顯示0的點，是不可以走的。小知每次只能到達相鄰的上下左右4個格子。
如何走？
1.如果當前出發的格子是終點，則程序結束。
2.每次可以選擇的格子有：上(A)、下(B)、左(C)、右(D)。
3.按照順序嘗試每個格子是否可走。
4.找到第一個可以走的格子(假設為B)，標記該格子，表示已經走過。
5.再從格子(B)出發，重復上述過程(遞歸進行)。
6.將格子(B)消除標記，再嘗試從格子(C、D)出發去找路線。
?
問題建模
如何表示迷宮地圖等信息呢？
使用一個3*3的二維數組maze[][]來存儲迷宮信息，如果值位0表示不可走，1表示可走。
使用一個3*3的二維數組used[][]來標記是否走過，沒走過為0，走過的話為1。
例：used[1][2]=1，表示maze[1][2]已經走過。
如何表示每次移動的過程？
每次移動，實際上就是坐標的變化。
上：行標-1，列標不變。
下：行標+1，列標不變。
左：行標不變，列標-1。
右：行標不變，列標＋1。
我們可以用一個二維數組表示移動的方向。
例：當前坐標為(1,2)，向上移動就是：(1+fx[0][0],2+fx[0][1])，得到(0,2)。
?
走迷宮問題參考程序
int ans=0,maze[6][6],used[6][6],fx[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
void dfs(int x,int y){if(x==3&&y==3){ //如果當前找的點就是終點，則方案數+1，結束本次搜索。ans++; return ;}else{used[x][y]=1; //將當前所在的點標記為1，表示走過for(int i=0;i<4;i++) { //嘗試上、下、左、右4個方向int nx=x+fx[i][0];int ny=y+fx[i][1]; //下一次查找的點的坐標nx，ny//nx,ny要在地圖內,并且可走，并且未被走過。if(nx>=1&&nx<=3&&ny>=1&&ny<=3&&used[nx][ny]==0&&maze[nx][ny]==1){used[nx][ny]=1; //表示nx，ny表示走過dfs(nx,ny); //從nx，ny再去找used[nx][ny]=0; //消除標記，再嘗試其他方向。}}used[x][y]=0; //消除標記}
}int main(){for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){cin>>maze[i][j];}}dfs(1,1);cout<<ans;return 0;
}
深度優先搜索概述
我們走迷宮的過程就是一個深度優先搜索的過程：從可以解決問題的某一個方向出發，并一直深入尋找，找到這個方向可以得到的所有解決方案，如果找不到，則回退到上一步，從另一個方向開始，再次深入尋找。
解決問題時的注意事項
1.首先弄清楚問題的解空間，即迷宮有多大。
2.弄清楚搜索的邊界，即到哪一步就該停下，不用再搜。
3.搜索的方向，即可能包含哪幾種子問題。
void dfs()//參數用來表示狀態
{ if(到達終點狀態){ ...//根據題意添加 return; } if(越界或者是不合法狀態) return; if(特殊狀態)//剪枝return ;for(所有可能的下一狀態){ if(狀態符合條件){ 修改操作;//根據題意來添加 標記; dfs(); (還原標記); //是否還原標記根據題意 //如果加上（還原標記）就是 回溯法 } }
}
訓練：迷宮
給定一個N*M方格的迷宮，迷宮里有T處障礙，障礙處不可通過。給定起點坐標和終點坐標，問: 每個方格最多經過1次，有多少種從起點坐標到終點坐標的方案。在迷宮中移動有上下左右四種方式，每次只能移動一個方格。數據保證起點上沒有障礙。
【輸入描述】第一行N、M和T，N為行，M為列，T為障礙總數。第二行起點坐標SX,SY，終點坐標FX,FY。接下來T行，每行為障礙點的坐標。
【輸出描述】給定起點坐標和終點坐標，問每個方格最多經過1次，從起點坐標到終點坐標的方案總數。
【輸入樣例】2 2 1
1 1 2 2
1 2
【輸出樣例】1
參考代碼
#include<bits/stdc++.h>
using namespace std;int ans=0,maze[6][6],used[6][6];
int Fx[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,m,t,sx,sy,fx,fy,tx,ty;void dfs(int x,int y,int s,int e){if(x==s&&y==e){ans++; return ;}else{used[x][y]=1;for(int i=0;i<4;i++) {int nx=x+Fx[i][0];int ny=y+Fx[i][1];if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&used[nx][ny]==0&&maze[nx][ny]==0){ used[nx][ny]=1;dfs(nx,ny,s,e);used[nx][ny]=0;}}used[x][y]=0;}
}int main(){cin>>n>>m>>t;cin>>sx>>sy>>fx>>fy;for(int i=1;i<=t;i++){cin>>tx>>ty;maze[tx][ty]=1;}dfs(sx,sy,fx,fy);cout<<ans;return 0;
}
訓練：全排列問題
輸入整數n(n<=9)，輸出1~n的所有排列方式。
例：n=3，全排列為123，132，213，231，312，321。
【輸入描述】輸入一個正整數n
【輸出描述】輸出1~n之間的全排列（n<=9），換行輸出
【輸入樣例】3
【輸出樣例】123
132
213
231
321
312
參考代碼
int ans[10],used[10];
void dfs(int x,int n){if(x>n){for(int i=1;i<=n;i++)cout<<ans[i];cout<<endl;return;}for(int i=1;i<=n;i++){if(!used[i]){ans[x]=i;used[i]=1;dfs(x+1,n);used[i]=0;}}
}
int main(){int n;cin>>n;dfs(1,n);return 0;
}從入門到算法，再到數據結構，查看全部文章請點擊此處??
http://www.bigbigli.com/?
