AcWing 842. 排列数字 && AcWing 843. n-皇后问题

发布时间 2023-12-04 11:42:29作者: 爬行的蒟蒻

842. 排列数字(全排列)

题面:
给定一个整数 \(n\),将数字 \(1∼n\) 排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。

#include <iostream>
using namespace std;

const int N = 10;
int path[N];//保存序列
bool st[N];//数字是否被用过,bool类型的全局变量默认都为FALSE
int n;	//n定义全局,则dfs函数不需要两个参数?

void dfs(int u)
{
	if (u == n) {	//u始终未变,保证每次都是从头开始遍历
		for (int i = 0; i < n; i++)		//此时st数组里面一定全是1,不会进入下面的for循环
			cout << path[i] << " ";
		cout << endl;
		//puts(" ");
		return;		//回溯操作在return,return完这个递归就结束了
	}
	for (int i = 1; i <= n; i++) {	//退出dfs不仅靠return,循环结束即意味着函数结束
		if (!st[i]) {	//当前该数没有被用过
			path[u] = i;
			st[i] = true;
			dfs(u + 1);
			st[i] = false;		//逐个退出函数,逐个恢复现场
		}
	}
}

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

843. n-皇后问题

题面:
\(n\) 个皇后放在 \(n×n\) 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 \(n\) ,请你输出所有的满足条件的棋子摆法。

#include <bits/stdc++.h>
using namespace std;

const int N = 10;
int n;
char m[N][N];
bool col[N], dg[N], udg[N];	//列,对角,反对角

void dfs(int u) {
	int x = u;	//逐行递归
	for (int y = 0; y < n; y++) {
		//在经过的列/对角线/反对角线上该点都没有其余皇后
		if (!col[y] && !dg[x + y] && !udg[n - x + y]) {
			m[x][y] = 'Q';
			col[y] = dg[x + y] = udg[x + y] = true;
			dfs(x + 1);
			col[y] = dg[x + y] = udg[x + y] = false;
			m[x][y] = '.';
		}
	}
	//递归达到最大深度,输出整行
	if (u == n) {
		for (int i = 0; i < n; i++)
			cout << m[i] << endl;
		cout << endl;
	}
}

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