51-N皇后

class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<vector<string>>res; // 存储最终结果 vector<string>temp(n, string(n, '.')); vector<int>col(n, 0); // 存储已有的列值 vector<int>dg(2 * n, 0); // 存储已有的正对角线的值 vector<int>adg(2 * n, 0); //存储已有的反对角线的值 dfs(0, n, res, temp, col, dg, adg); return res; } void dfs(int row, int n, vector<vector<string>>&res, vector<string>temp, vector<int>col, vector<int>dg, vector<int>adg) { if (row == n) { res.push_back(temp); } for (int i = 0; i < n; i++) { if (!col[i] && !dg[row - i + n] && !adg[row + i]) { //将该位置的列，正对角线，反对角线的值都置为1 col[i] = dg[row - i + n] = adg[row + i] = 1; temp[row][i] = 'Q'; //设置Q; dfs(row + 1, n, res, temp, col, dg, adg); //深度优先搜索 col[i] = dg[row - i + n] = adg[row + i] = 0; // 重置，以便下次查找合适的位置 temp[row][i] = '.'; } } } };