LeetCode 51. N皇后
原题链接
困难
作者:
linux_2019
,
2019-09-14 14:17:30
,
所有人可见
,
阅读 1230
C++ 代码
class Solution {
public:
vector<bool> col,dg,udg;
int cnt;
vector<vector<string>> ans;
vector<vector<char>> ui;
string t;
vector<string> path;
void dfs(int u)
{
if(u==cnt)
{
for(int i=0;i<cnt;i++)
{
for(int j=0;j<cnt;j++)
t+=ui[i][j];
path.push_back(t);
t.clear();
}
ans.push_back(path);
path.clear();
return ;
}
for(int i=0;i<cnt;i++)
{
if(!col[i]&&!dg[u+i]&&!udg[cnt+u-i])
{
col[i]=dg[u+i]=udg[cnt+u-i]=1;
ui[u][i]='Q';
dfs(u+1);
ui[u][i]='.';
col[i]=dg[u+i]=udg[cnt+u-i]=0;
}
}
}
vector<vector<string >> solveNQueens(int n) {
cnt=n;
col.resize(n);
dg.resize(2*n);
udg.resize(2*n);
ui=vector<vector<char >>(n,vector<char >(n));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
ui[i][j]='.';
dfs(0);
return ans;
}
};