N-Queens first hard
这与八皇后问题并无本质区别，通过一个一维数组vis记录每一行第几个位置拜访皇后，再往下递归时判断是否与之前拜访的皇后在同一列，同一正对角线，同一副对角线上，最后将本次递归的结果pop，以进行下次递归。
bool available(vector<int> &vis, int row, int col) { for (int i = 0; i<row; i++) { if (vis[i] == col)return false; if ((i - vis[i]) == (row - col))return false; if ((i + vis[i]) == (row + col))return false; } return true; } void nQueensDFS(vector<vector<string>> &res, vector<int> &vis, vector<string> &out, int level, int n) { if (level == n) { res.push_back(out); } else { for (int i = 0; i<n; i++) if (available(vis, level, i)) { vis[level] = i; string tem=""; for (int j = 0; j<n; j++) { if (j == vis[level])tem += 'Q'; else tem += '.'; } out.push_back(tem); nQueensDFS(res, vis, out, level + 1, n); vis[level] = -1; out.pop_back(); } } } vector<vector<string>> solveNQueens(int n) { vector<vector<string>> res; vector<int> vis(n, -1); vector<string> out; int level = 0; nQueensDFS(res, vis, out, level, n); return res; }
