C++：第十一讲DFS深搜

Everyday English

Your optimal career is simply this: Share the real you with physical world through th e process of creative self-expression.
你的最佳职业很简单，就是这样：通过创造性自我表达的途径和世界分享真实的你。

前言

今天带着大家学习一个既简单又重要的算法——深搜函数DFS。

DFS

一、基本思想

为了求得问题的解，先选择某一种可能情况向前探索；
在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索；
如此反复进行，直至得到解或证明无解

二、搜索算法

搜索算法，就是利用计算机的高性能，对问题的“状态空间”进行枚举，穷举出一个问题的全部或者部分可能的情况，找到最优解或者统计合法解的个数。在搜索算法中，深度优先搜索算法（Depth First Search，DFS，简称深搜），常常指利用递归函数方便地实现暴力枚举的算法，也称为“回溯法”。通过递归函数，我们可以逐层地枚举每一种可能，从而实现枚举所有可能的“状态”。搜索算法是一些高级算法的基础，而搜索算法可以在很多问题中解决数据范围较小的部分。掌握正确的写搜索算法，对后续高级算法的学习和理解有着一定的帮助。

三、深搜模版（C++）

vector<int> a; // 记录每次排列 
vector<int> book; //标记是否被访问 

void DFS(int cur, int k, vector<int>& nums){
    if(cur == k){ //k个数已经选完，可以进行输出等相关操作 
        for(int i = 0; i < cur; i++){
			printf("%d ", a[i]);
		} 
        return ;
    }
    for(int i = 0; i < k; i++){ //遍历 n个数，并从中选择k个数 
        if(book[nums[i]] == 0){ //若没有被访问
            a.push_back(nums[i]); //选定本输，并加入数组 
            book[nums[i]] = 1; //标记已被访问 
            DFS(cur + 1, n, nums); //递归，cur+1 
            book[nums[i]] = 0; //释放，标记为没被访问，方便下次引用 
            a.pop_back(); //弹出刚刚标记为未访问的数
        }
    }
}

例题（洛谷P1706全排列问题）

题目描述

按照字典序输出自然数 1到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数n。

输出格式

由1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 5个场宽。

输入输出样例

输入 #1

输出 #1

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

说明/提示

1≤n≤9。

解题思路

根据题意，对于全排列问题，以样例n=3为例，可以深度优先DFS搜索方法如图所示。

根据上述搜索过程，设计算法步骤如下：（1）用数组a保存排列，当排列的长度为n时，是一种排列方案，输出即可。（2）用数组vis记录数字是否被使用过，当vis[i]=1时，表示数字i被使用过，否则没有被使用过。（3）DFS(u)表示已经确定了a的前u个数（从a[1]开始填数），当u>n时，输出搜索的全排列。注意：在DFS过程中，数组vis既要标记，也要“撤销”标记。

AC

#include<bits/stdc++.h>
using namespace std;
int a[10],n;
bool vis[10];
void dfs(int u){
	if(u>n){//当u=n+1时，表示前n个空位已填好数 
		for(int i=1;i<=n;i++){//输出一种排列方案 
			cout<<setw(5)<<a[i];
		}
		cout<<endl;
		return;//dfs的终止条件 
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			a[u]=i;//在第u个空位填上i 
			vis[i]=1;//标记i为已使用 
			dfs(u+1);//填下一个空位 
			vis[i]=0;//dfs回来后，要撤销之前的标记 
		}
	}
}
int main(){
	cin>>n;
	dfs(1);
	return 0;
}

setw函数

格式：
setw(……)//()内是数字
setw（）——打印格式（控制）
setw means:宽度
E.X.
setw(4):
0 0 0 0//每个隔4格
！只适用于打印字符！

洛谷小课堂P1605 迷宫

题目描述

给定一个 N×M 方格的迷宫，迷宫里有T处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 N,M,T，分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 SX,SY,FX,FY，SX,SY 代表起点坐标,FX,FY 代表终点坐标。

接下来 T 行，每行两个正整数，表示障碍点的坐标。

输出格式

输出从起点坐标到终点坐标的方案总数。

输入输出样例:

输入 #1

2 2 1
1 1 2 2
1 2

输出 #1

说明/提示

对于 100%的数据，1≤N,M≤5，1≤T≤10，1≤SX,FX≤n，1≤SY,FY≤m。

解题思路

这题除了深搜，还是深搜。

深搜，一句话来总结一下，就是：

不撞南墙不回头

而在这题里，“南墙”有三个：

第一个是真墙：迷宫的围墙

也就是俗话所说的越界。越界了你还不回头，你是想去哪儿？

第二个是山墙:障碍物T

如果一障碍物横在你面前，你还是绕路吧！

第三个是人造墙：题目说了每个方格最多只能走一次

这是真没办法

所以深搜的返回条件就出来了——就是以上那三堵墙

我们每次可以从上下左右四个方向进行深搜，一旦遇上南墙就返回。

AC

#include<iostream>
using namespace std;
int n, m, t, sx, sy, fx, fy;
int  vis[10][10]; //标记
int mp[10][10]; //障碍物位置
int ans = 0;
int xx[] = { 1,0,-1,0 };
int yy[] = { 0,-1,0,1 };
void dfs(int x, int y)
{
    if (x == fx && y == fy)
    {
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int dx = xx[i] + x;
        int dy = yy[i] + y;
        if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && vis[dx][dy]==0 && mp[dx][dy]==0)
        {
            vis[dx][dy] = 1;
            dfs(dx, dy);
            vis[dx][dy] = 0;
        }
    }
}
int main()
{
    cin >> n >> m >> t >> sx >> sy >> fx >> fy;
    while (t--)
    {
        int a, b;
        cin >> a >> b;
        mp[a][b] = 1;
    }
    vis[sx][sy] = 1;
    dfs(sx, sy);
    cout << ans << endl;
    return 0;
}

课后练习：洛谷P2404 自然数的拆分问题

题目

自然数的拆分问题 - 洛谷

解题思路

dfs递归求解，假设1到n-1每个数都有n个，现在在这n(n-1)个数里选取任意个数字，使这些数字的和为n,因此这n(n-1)个数只有选和不选两种状态，正是dfs的经典应用，得到的结果可能会有重复的

所有可以用sort和set进行排序和去重步骤

AC

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
vector<int>a;
string midd;
set<string>h;
int n,t;
 
void dfs(int mid){
    if(mid==n){         //如果数的累加和等于n就记录该组合
        t++;
        vector<int>b(a);   //复制数组a
        sort(b.begin(),b.end());     //排序
        midd.clear();
        for(int i=0;i<b.size();i++){          //把整数数组转换成字符串，并存入set里去重
            midd+=(b[i]+'0');
            if(i<b.size()-1) midd+='+';
        }
        h.insert(midd);
    }
 
    for(int i=1;i<n;i++){
        if(mid+i<=n){
            mid+=i;
            a.push_back(i);
            dfs(mid);               //每一层都加入i并递归到下一层（选）
            a.pop_back();           //回溯，使得这一层不加入i（不选）
            mid-=i;
        }
    }
}
 
int main(){
    cin>>n;
    dfs(0);
    for(auto i:h)
      cout<<i<<endl;
 
    return 0;
}