DFS应用—全排列

AcWing 842. 排列数字

给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式
共一行，包含一个整数n。

输出格式
按字典序输出所有排列方案，每个方案占一行。

数据范围
1≤n≤7

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

这道题也就是搜索 1~n 的一个全排列问题

按照样例 n=3，首先，第0个位置可以填1 / 2 / 3，这里如果先填1的话，那么第一个位置可以填 2 / 3，填2的话，第二个位置只能填3了，此时{1、2、3}就是其中一个答案，然后我们再回溯，第二个位置还可以填3，那么{1、3、2}就是一个答案了，依次类推。

#include<iostream>
using namespace std;
const int N=10;
int n;
int path[N]; //path只会存当前的一条路径，再回溯时这条路径就没有了
bool st[N]; // 标记已经有哪些数被用过了 

void dfs(int u)
{
	if(u == n) // 当递归到第n个位置时，说明0~n-1位置已经填满 
	{
		for(int i=0; i<n; i++) cout << path[i] << " ";
		cout<<endl;
		return;
	}
	
	 // 0~n-1位置上的数没填完，枚举第 u 个位置上应该填哪个数
	for(int i=1; i<=n; i++) 
	  if(!st[i])  // i没有被用过
	  {
	     path[u] = i; // 把 i 放到当前位置 
		 st[i] = true; // 标记 i 已经用过了
		 dfs(u+1);  // 递归到下个位置 
		 st[i] = false; // 恢复现场	
	  } 
}
int main()
{
	cin >> n;
	dfs(0); //从第 0 个位置开始 
	return 0;
}

---

AcWing 843. n-皇后问题

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

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

输入格式
共一行，包含整数n。

输出格式
每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。

其中”.”表示某一个位置的方格状态为空，”Q”表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围
1≤n≤9

输入样例：
4

输出样例：
.Q…
…Q
Q…
…Q.

…Q.
Q…
…Q
.Q…

这道题的思路其实和上面的那道题一样，都是全排列的思想。因为每一行都要有一个皇后，而且每一行的皇后都不能在同一列上，我们可以像上道题一样，画 n 个空位，第 0 个位置代表第 0 行的皇后放到某一列上，第 1 个位置代表第 1 行的皇后放到某一列上…。

#include<iostream>
using namespace std;
const int N=20; // 对角线的个数是2*N-1
int n;
char g[N][N];
bool col[N],dg[N],udg[N];// 同一列、正对角线、反对角线 

void dfs(int u)  
{
   if(u == n) //找到一组方案，输出 
   {
   	  for(int i=0; i<n; i++)
   	  {
   	  	for(int j=0; j<n; j++)
   	  	 cout<<g[i][j];
   	  	cout<<endl; 
	  }
	  cout<<endl; 
   	   return; 
   }	
   
   for(int i=0; i<n; i++)   //枚举第 u 行的皇后应该放在哪一列
     if(!col[i] && !dg[u+i] && !udg[n-u+i]) //这一列、这条对角线、反对角线必须都没有皇后才可以
	 {
	 	g[u][i] = 'Q'; // 第u行的皇后放到第i列 
	 	col[i] = dg[u+i] = udg[n-u+i] = true;
		dfs(u+1); //递归到下一行
		col[i] = dg[u+i] = udg[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);  //从第 0 行开始 
	return 0;   
}