DFS

咳咳，先来说一下神马是DFS。

DFS就是深搜，深度优先搜索。

也是让一些像我一样的弱弱头疼的一件事。

那具体什么又是深搜腻？让我们通过这张图片了解一下。

红色是深搜搜索路线。

大家一看也就明白了：深搜就是在每个节点不停往深里搜索的搜索方法。

接下来说说回溯。

神马是回溯？就是在搜索一个枝杈后返回的过程。

还有，回溯必须要

还原现场！！！

还原现场！！！

还原现场！！！

重要的事情说三遍。

打一个y总说过的比方：回溯就相当于父母把你放在家里，自己出去，如果你把房间弄乱了，后果可想而知。

回溯也是这个道理。

回溯的代码一般是这样滴：

for(int i = 0/*(也可能是别的)*/; i < /*...*/;i ++ /*(或--)*/)
{
    st[i] = true;//节点被访问
    /*......*/;//干一些操作
    dfs(u + 1); // 递归下一层
    st[i] = false;
    /*......*/;//还原现场，回溯
}

然后给大家看一下DFS模板

const int N = ;//N看题目数据范围

int n;
bool st[N];//存节点是否被访问过
char x[N];//存状态，可能是二维，也可能是多个

void dfs(int u)
{
    if(u == n)//无需搜索
    {
        for(int i = ;i ;i ) 
        {
            cout << ;//输出
        }
        return;
    }
    for(int i = ;i ;i )//搜索
    {
        //下面是上面的那个回溯模板
        st[i] = true;//节点被访问
        /*......*/;//干一些操作
        dfs(u + 1); // 递归下一层
        st[i] = false;
        /*......*/;//还原现场，回溯
    }
}

接下来看两道题（算法基础课DFS里的排列数字和n—皇后问题）

1、排列数字

题目描述

给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。

数据范围

1≤n≤7

样例

输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 10;//多几个也无妨

int n;
int path[N];
bool st[N];

void dfs(int u)//上述模板部分
{
    if(u == n)
    {
        for(int i = 0; i < n; i ++) cout << path[i] << ' ';//输出
        cout << endl;
        return;
    }
    for(int i = 1;i <= n; i ++)
    {
        if(!st[i])
        {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);//递归
            st[i] = false;//还原现场
            path[u] = 0;
        }
    }
}

int main()
{
    cin >> n;
    dfs(0);
    return 0;
}

这就是本题的代码

2、n-皇后问题

题目描述

n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数n，请你输出所有的满足条件的棋子摆法。

数据范围

1≤n≤9

样例

输入样例：
4
输出样例：
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

代码

#include<iostream>

using namespace std;

int n;
char g[20][20];
bool c[20],d[20],ud[20];

void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0 ;i < n; i ++) cout << g[i] << endl;//输出
        cout << endl;
        return;
    }
    for(int i = 0; i < n; i ++)
        if(!c[i] && !d[u + i] && !ud[n - u + i])
        {
            c[i] = d[u + i] = ud[n - u + i] = true;
            g[u][i] = 'Q';
            dfs(u + 1);//递归
            c[i] = d[u + i] = ud[n - u + i] = false;//还原现场
            g[u][i] = '.';
        }
}

int main()
{
    cin >> n;
    for(int i = 0;i < n; i ++)
        for(int j = 0; j < n;j ++) 
            g[i][j] = '.';
    dfs(0);
    return 0;
}

好了，今天我们就先说到这里。

还有，大家可以看看闫老师在算法基础课里的讲解哦！

bye！！！