[//]: # N皇后问题 Leetcode版本
C++ 代码
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
for (int i = 0; i < n; i++)
{
string row;
for (int j = 0; j < n; j++)
row.push_back('.');
grid.push_back(row);
col.push_back(false);
dg.push_back(false);
udg.push_back(false);
dg.push_back(false);
udg.push_back(false);
}
dfs(0, n);
return res;
}
private:
vector<string> grid;
vector<vector<string>> res;
vector<bool> col, dg, udg;
void dfs(int u, int n)
{
if (u == n)
{
res.push_back(grid);
return;
}
for (int i = 0; i < n; i++)
{
if (!col[i] && !dg[u + i] && !udg[n + u - i - 1])
{
grid[u][i] = 'Q';
col[i] = dg[u + i] = udg[n + u - i - 1] = true;
dfs(u + 1, n);
col[i] = dg[u + i] = udg[n + u - i - 1] = false;
grid[u][i] = '.';
}
}
}
};