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 a; // 记录每次排列 vector book; //标记是否被访问 void DFS(int cur, int k, vector& 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
3
输出 #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 #includeusing 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 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