Leetcode 51 N Queens Leetcode N Queens II

题意

给定一个数字$n$，形成n*n的棋盘，棋盘上放n个皇后，确保皇后之间不会相互吃（皇后可以直线吃，斜线吃）

链接

https://leetcode.com/problems/n-queens/description/

思考

这道题只能暴力枚举所有的位置，但是如果直接在二维矩阵上做空间复杂度比较高，可以降维度

题解

dfs枚举所有可以放n皇后的地方。构造一个数组pos,$pos[i]$代表在第i行第pos[i]列放一个皇后。
结束条件为，当pos数组长度为n，根据pos数组构造二维的答案
传入参数u表示当前pos数组添加到第几个元素（实际上是第u行皇后应该放在什么位置），遍历这个元素所有的可能性（0-n 列），并且判断新放入皇后是否和前面所有的皇后列数相同，是否和前面所有的皇后在同一个对角线上，如果不在，那么第u位就选了，要选择第u+1位元素，注意回溯。

对角线性质

class Solution {
public:vector<vector<string>> res; vector<vector<string>> solveNQueens(int n) {//pos保证所有的n queens不可能在同一行，所以循环中只需要check//是不是同一列或者斜对角就可以vector<int> pos;dfs(0, pos, n);return res;}void dfs(int u, vector<int>& pos, int n) {if( u == n ) {vector<string> str(n, string(n, '.'));for(int i = 0; i < n; i++) {str[i][pos[i]] = 'Q';}res.push_back(str);return;}for(int i = 0; i < n; i++) {if(isValid(pos,u, i)) {pos.push_back(i);dfs(u+1, pos, n);pos.pop_back();}}}bool isValid(vector<int>& pos, int row, int col) {int m = pos.size();for(int i = 0; i < m; i++) {int preRow = i;int preCol = pos[i];if(col == preCol) return false;if(abs(row-preRow) == abs(col - preCol)) return false;}return true;}
};

时间复杂度：$O(N^2\ast N!)$
空间复杂度：$O(N)$

N Queens II是统计所有不同的方案数，一样的解法

class Solution {
public:int cnt = 0;int totalNQueens(int n) {vector<int> pos;dfs(0, pos, n);return cnt;}void dfs(int u, vector<int>& pos, int n) {if( u == n) {cnt++;return;}static vector<bool> col(n, false);static vector<bool> diag(2*n-1, false);static vector<bool> udiag(2*n-1, false);        for(int i = 0; i < n; i++) {int r = u;int c = i;if(!col[c] && !diag[r+c] && !udiag[r-c+n-1]) {pos.push_back(i);col[c] = diag[r+c] = udiag[r-c+n-1] = true;dfs(u+1, pos, n);col[c] = diag[r+c] = udiag[r-c+n-1] = false;pos.pop_back();}}}
};

时间复杂度：$O(N^2\ast N!)$
空间复杂度：$O(N)$