[数据结构与算法]n-皇后问题 （dfs）(与leetcode题相同)

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

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

输入格式

共一行，包含整数 n。

输出格式

每个解决方案占 n行，每行输出一个长度为 n的字符串，用来表示完整的棋盘状态。其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

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

数据范围

1≤n≤9

输入样例：

4

输出样例：

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

处理对角线问题：

根据x和y可以找到某个点属于的对角线，用截距表示。

思路：

深度优先搜索，不满足的情况剪枝。

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
bool col[N],dg[N],udg[N];
char g[N][N];
int n;
void dfs(int u) {
	if (u == n) {
		for (int i = 0; i < n; i++)puts(g[i]);
		cout << endl;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
			g[u][i] = 'Q';
			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);
	return 0;
}

leetcode代码：

const int N = 20;
class Solution {
public:
bool col[N],dg[N],udg[N];
char g[N][N];
void dfs(int u,int n,vector<vector<string>> &s){
    if(u==n){
        vector<string> ans;
        for(int i=0;i<n;i++){
            string res = g[i];
            ans.push_back(res);
        }
        s.push_back(ans);
    }
    for (int i = 0; i < n; i++) {
		if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
			g[u][i] = 'Q';
			col[i] = dg[u + i] = udg[n - u + i] = true;
			dfs(u + 1,n,s);
			col[i] = dg[u + i] = udg[n - u + i] = false;
			g[u][i] = '.';
		}
	}
}
    vector<vector<string>> solveNQueens(int n) {
        for (int i = 0; i < n; i++)
		    for (int j = 0; j < n; j++)g[i][j] = '.';
        vector<vector<string>> s;
        dfs(0,n,s);
        return s;
    }
};