DFS深度优先搜索

(23条消息) DFS入门级（模板）_?江晚吟的博客-CSDN博客_dfs入门

思路：

1. 所谓DFS就是指：优先考虑深度，换句话说就是一条路走到黑，直到无路可走的情况下，才会选择回头，然后重新选择一条路。
2. 用book函数来存储是否走过一次,用a[step]来表示盒子，step为盒子的下标，i为扑克牌的面值
3. 记得回溯操作
4. 如果扑克牌没使用过（book[i]==0）就把它放进盒子里（a[step]=i），并把它的状态标记为1(book[i]=1)，然后进行下一个盒子的操作(dfs(step+1)自我递归调用)
5. 盒子里全部装满(step==n+1)表示一条路走完了，再开始走第二条路（，开始重新选择（DFS的思想），这里要注意的，不是把所有的牌都取出来重新放，这样就不符合DFS的思想了。）（return）直到全部走完

基本模型

void dfs(int step){

判断边界

尝试每一种可能 for(i=1;i<=n;i++){

继续下一步 dfs(step+1)

}

返回}

模板

假如有编号为1,2,3的3张扑克牌和编号为1,2,3的3个盒子。将这3张扑克牌分别放入3个盒子一共有几种不同的放法呢？

#include
using namespace std;
long long book[100]={0};
long long a[100];
long long n;
void dfs(long long step)
{
    if(step==n+1)
    {
        for(int i=1;i<=n;i++)
        cout<<a[i];    
        cout<<endl;
        return;
    }

    for(int i=1;i<=n;i++)
    {
        if(book[i]==0)
        {
            book[i]=1;
            a[step]=i;
            dfs(step+1);
            book[i]=0;//回溯
        }
    }
    return;
}
int main()
{
    cin>>n;
    dfs(1);
    return 0;
}

迷宫问题：

1. 设step的初值是零更方便些
2. a表示路况
3. Book表示是否走过
4. 路况不可改变，改变的是book的状态
5. 用数组来模拟移动

#include
using namespace std;
long long minn=999;
long long book[100][100]={0};
long long a[100][100];
long long m,n,s1,s2,e1,e2;
long long dir[4][2]={1,0,-1,0,0,1,0,-1};
long long cnt=0;
void dfs(long long x,long long y,long long step)
{
    if(x==e1&&y==e2)
    {
        if(step<minn)
        minn=step;
        //cout<//cout<
        return;
    }
    for(int i=0;i<4;i++)
    {
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        //必须满足路况是0（可以走），而且状态是0 （没走过） 
        if(tx>=1&&tx<=m&&ty>=1&&ty<=n&&a[tx][ty]!=1&&book[tx][ty]!=1) 
        {
            book[tx][ty]=1;
            dfs(tx,ty,step+1);
            book[tx][ty]=0;
        }
        cnt++;
    }
    return;
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    {
        cin>>a[i][j];
    }
    cin>>s1>>s2>>e1>>e2;
    a[s1][s2]=1;
    dfs(s1,s2,0);
    cout<endl;
    //cout<
    return 0;
}

简单的对以前在word中的算法笔记进行整理，自用，参考标注不完整，侵删