Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
思路：II比I简单，只需在I的基础上不打印计数即可。
class Solution {
private:
vector<bool> used;
vector<vector<bool> > queen;
int total;
public:
bool isAdj(int row, int col)
{
int n = queen.size();
int i,j;
i = row-1, j = col - 1;
while(i>=0 && j>=0)
{
if (queen[i][j])
{
return true;
}
i--,j--;
}
i = row - 1, j = col + 1;
while(i>=0 && j<n)
{
if (queen[i][j])
{
return true;
}
i--,j++;
}
return false;
}
void solveNQueensHelper(int pos,int n)
{
if (pos == n)
{
total++;
return;
}
int i;
for(i=0; i<n; ++i)
{
if (!used[i] && !isAdj(pos,i))
{
used[i] = true;
queen[pos][i] = true;
solveNQueensHelper(pos+1,n);
used[i] = false;
queen[pos][i] = false;
}
}
}
int totalNQueens(int n) {
used.clear();
queen.clear();
total = 0;
if (n <= 0)
{
return total;
}
used.resize(n);
queen.resize(n);
int i,j;
for(i=0; i<n; ++i)
{
used[i] = false;
queen[i].resize(n);
for(j=0; j<n; ++j)
{
queen[i][j] = false;
}
}
solveNQueensHelper(0,n);
return total;
}
};