最易懂的搜索与回溯算法（c++）

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

首先的例题是：迷宫

设有一个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;

}

看完这篇文章后，你对深度优先搜索有了更深的了解吗？欢迎在讨论区评论。