Leetcode 51 N Queens

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

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

题解：首先这是一道dfs，枚举所有可以放n皇后的地方。构造一个数组pos,$pos[i]$代表在第i行第j列放一个皇后。当数组满足长度要求时dfs结束。传入参数u表示当前我需要在第u行加入一个皇后，遍历所有n列，判断我皇后是否可以放入，如果可以放，那么就放，进入下一层dfs

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)$