【leetcode】51.N皇后

 

class Solution {
public:vector<vector<string>> ans; // 存储的最终结果vector<string> path; // 存储当前的一种放置方式vector<int> col, dg, undg; // 标志 列、斜对角线、正对角线上是否有Qvoid dfs(int u, int n) {if (u == n) { // 当深搜到第n行时，说明前n行（0~n-1）都已经有Q了，保存结果并返回ans.push_back(path);return;}for (int i = 0; i < n; i++) {if (col[i] == 0 && dg[n - 1 - u + i] == 0 && undg[u + i] == 0) {path[u][i] = 'Q';col[i] = 1;dg[n - 1 - u + i] = 1;undg[u + i] = 1;dfs(u + 1, n);path[u][i] = '.';col[i] = 0;dg[n - 1 - u + i] = 0;undg[u + i] = 0;}}}vector<vector<string>> solveNQueens(int n) {col.resize(n, 0);dg.resize(2 * n - 1, 0);undg.resize(2 * n - 1, 0);path.resize(n, string(n, '.'));int u = 0;dfs(u, n); // 开始第 0 行return ans;}
};