DFS即深度优先搜索

适用于将一个问题的所有方面全部展开

 

acwing842即这么一个问题 ： 问题传送门：https://www.acwing.com/activity/content/problem/content/905/1/

主要是记录下没有基本模板的dfs需要注意的基本问题，也是使用dfs时的基本特点

 

本题是一个全排列问题：

将从1-n的n个数字的所有排列情况全部输出即可

 

以样例为例。

1-3共有3个位置

3个位置可以上3个数中的一个，若1号位置为1，则2号3号位置不能为1，只能为2或3；若2号位置为2，3号位置不能为1和2，只能为3.此时得到一组排列

以此类推我们可以得到共6种全排列。

 

关于DFS实现的问题：
需要注意

1.当一次搜索结束时，输出所有情况并回溯返回上一层

2.当返回上一层后，必须回复现场，即将标记过已被占用的位置恢复成未被占用

 

代码详解：
 

/*
dfs重点是顺序 
破坏完现场后再恢复现场 
*/
#include<iostream>

using namespace std;

const int N = 8;
int path[N]; //全排列数组，其中记录一次排列 
bool st[N];  //记录当前位置是否被占用了 

void dfs(int u){//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]){//该位置没被占用，则此时可占用 
			 path[u] = i; //给u号位上添数字
			 st[i] = true; //占用过了就记录下
			 dfs(u+1); //u号位置搜索过后，开始u+1号位的搜索
			 //搜索结束后恢复现场
			 st[i] = false;
			 path[u] = 0;
			 //这里也可不用恢复path[u]因为 path[u]再循环中会被直接赋值 
		}
}
int main()
{
	int n;
	cin >> n;
	
	dfs(0);
	
	return 0;
}