回溯算法實際上一個類似枚舉的搜索嘗試過程紊遵，主要是在搜索嘗試過程中尋找問題的解窄绒，當(dāng)發(fā)現(xiàn)已不滿足求解條件時，就“回溯”返回成洗，嘗試別的路徑五督。
首先的例題是：迷宮
設(shè)有一個N*N(2<=N<10)方格的迷宮，入口和出口分別在左上角和右上角瓶殃。迷宮格子中分別放0和1充包，0表示可通，1表示不能，入口和出口處肯定是0基矮。迷宮走的規(guī)則如下所示：即從某點開始淆储，有八個方向可走，前進(jìn)方格中數(shù)字為0時表示可通過家浇，為1時表示不可通過本砰，要另找路徑。找出所有從入口（左上角）到出口（右上角）的路徑(不能重復(fù))钢悲，輸出路徑總數(shù)点额，如果無法到達(dá)，則輸出0莺琳。
思路：直接想：一個小人站在左上角还棱，一遇到岔路口就會分身，假如最后被逼到墻角惭等，小人就會消失珍手，并把計數(shù)器加一，最后再輸出計數(shù)器的值就行了咕缎。
其中的小人其實就是函數(shù)珠十，分身就是遞歸一次，遞歸也是深度優(yōu)先搜索的一種實現(xiàn)操作凭豪。
代碼例子：
#include <iostream>
using namespace std;
int ans=0,sum=0,n,b[15][15]={0},dy[9]={1,-1,1,0,-1,1,0,-1},dx[9]={0,0,1,1,1,-1,-1,-1};
void execute(int xx,int yy){
? ? if(xx==1&&yy==n){
? ? ? ? ans++;
? ? ? ? return;
? ? }
? ? int i,x,y;
? ? for(i=0;i<=7;i++){
? ? ? ? x=xx+dx[i];
? ? ? ? y=yy+dy[i];
? ? ? ? if(b[x][y]==0&&x<=n&&y<=n&&x>=1&&y>=1){
? ? ? ? ? ? b[x][y]=1;
? ? ? ? ? ? execute(x,y);
? ? ? ? ? ? b[x][y]=0;
? ? ? ? }
? ? }
}
int main(){
? ? cin>>n;
? ? for(int c=1;c<=n;c++){
? ? ? ? for(int i=1;i<=n;i++){
? ? ? ? ? ? cin>>b[c][i];
? ? ? ? }
? ? }
? ? b[1][1]=1;
? ? execute(1,1);
? ? cout<<ans;
}
看完這篇文章后焙蹭，你對深度優(yōu)先搜索有了更深的了解嗎？歡迎在討論區(qū)評論嫂伞。
