回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
首先的例题是：迷宫
设有一个N*N(2<=N<10)方格的迷宫，入口和出口分别在左上角和右上角。迷宫格子中分别放0和1，0表示可通，1表示不能，入口和出口处肯定是0。迷宫走的规则如下所示：即从某点开始，有八个方向可走，前进方格中数字为0时表示可通过，为1时表示不可通过，要另找路径。找出所有从入口（左上角）到出口（右上角）的路径(不能重复)，输出路径总数，如果无法到达，则输出0。
思路：直接想：一个小人站在左上角，一遇到岔路口就会分身，假如最后被逼到墙角，小人就会消失，并把计数器加一，最后再输出计数器的值就行了。
其中的小人其实就是函数，分身就是递归一次，递归也是深度优先搜索的一种实现操作。
代码例子：
#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;
}
看完这篇文章后，你对深度优先搜索有了更深的了解吗？欢迎在讨论区评论。
