Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where
'Q'
and '.'
both indicate a queen and an empty space respectively.For example,
There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
vector<vector<int>> r;
vector<int> t;
dfs(r,n,t);
int num=r.size();
vector<vector<string>> result;
for (int i=0; i<num; i++)
{
vector<string> tmp;
for (int j=0; j<n; j++)
{
string t(n,'.');
t[r[i][j]]='Q';
tmp.push_back(t);
}
result.push_back(tmp);
}
return result;
}
bool isvalid(int i, vector<int> &r)
{
//
int s = r.size();
for (int j=0; j<s; j++)
{
if (r[j]==i || r[j]-i==j-s ||r[j]-i==s-j ) //Pay attention to here
return false;
}
return true;
}
void dfs(vector<vector<int>> &r, int n, vector<int> &t)
{
if (t.size()==n)
{
r.push_back(t); //There's no r.clear();
}
else
{
for (int i=0; i<n; i++)
{
if (isvalid(i,t))
{
t.push_back(i);
dfs(r,n,t);
t.pop_back(); //backtracking
}
}
}
}
};
No comments:
Post a Comment