51. N-Queens
使用isValid判断当前的位置是否合法
每次遍历一行，使用queenCol记录之前行的存储位置，一方面是用于判断合法，另一方面可以根据存储结果输出最终的结果
棋盘的斜线都是45°的，所以两个位置x的差值和y的差值应该是相等的
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
vector<vector<string> > result;
if(n <= )
return result;
vector<int> queenCol(n,-);
int curRow = ;
solveNQueens(curRow,result,queenCol,n);
return result;
}
void solveNQueens(int curRow,vector<vector<string> >& result,vector<int>& queenCol,int n){
if(curRow == n){
vector<string> res(n,string(n,'.'));
for(int i = ;i < n;i++)
res[i][queenCol[i]] = 'Q';
result.push_back(res);
return;
}
for(int i = ;i < n;i++){
if(isValid(queenCol,curRow,i)){
queenCol[curRow] = i;
solveNQueens(curRow + ,result,queenCol,n);
queenCol[curRow] = -;
}
}
}
bool isValid(vector<int> queenCol,int row,int col){
for(int i = ;i < row;i++){
if(queenCol[i] == col || abs(row - i) == abs(col - queenCol[i]))
return false;
}
return true;
}
}; 52. N-Queens II
这个题更像是51题的简化版，51题需要把所有的可能性输出出来，这个题只需要输出不同的个数。代码基本和51题差不多，依旧使用dfs遍历就好。
注意：result加了引用! curRow没加引用！
result最终要作为返回值获得结果，所有的搜索情况都公用这个result，但是curRow，不同的搜索，搜索的值应该不一样
class Solution {
public:
int totalNQueens(int n) {
if(n <= )
return ;
vector<int> queenCol(n,-);
int result = ;
int curRow = ;
totalNQueens(n,queenCol,result,curRow);
return result;
}
void totalNQueens(int n,vector<int>& queenCol,int& result,int curRow){
if(curRow == n){
result++;
return;
}
for(int i = ;i < n;i++){
if(isValid(queenCol,curRow,i)){
queenCol[curRow] = i;
totalNQueens(n,queenCol,result,curRow+);
queenCol[curRow] = -;
}
}
}
bool isValid(vector<int>& queenCol,int row,int col){
for(int i = ;i < row;i++){
if(queenCol[i] == col || abs(row - i) == abs(col - queenCol[i]))
return false;
}
return true;
}
};另一种写法：
这种写法也是正确的，将queenCol的引用去掉，然后将queenCol[curRow] = -1;删掉，因为实际上不会回调回来。
如果你想用回调回来的，就必须queenCol[curRow] = -1
如果不用回调，其实queenCol[curRow] = -1这句话删掉不删掉都是正确的，因为不影响原来调用的函数中queenCol的结果。
class Solution {
public:
int totalNQueens(int n) {
if(n <= )
return ;
vector<int> queenCol(n,-);
int result = ;
int curRow = ;
totalNQueens(n,queenCol,result,curRow);
return result;
}
void totalNQueens(int n,vector<int> queenCol,int& result,int curRow){
if(curRow == n){
result++;
return;
}
for(int i = ;i < n;i++){
if(isValid(queenCol,curRow,i)){
queenCol[curRow] = i;
totalNQueens(n,queenCol,result,curRow+);
//queenCol[curRow] = -1;
}
}
}
bool isValid(vector<int>& queenCol,int row,int col){
for(int i = ;i < row;i++){
if(queenCol[i] == col || abs(row - i) == abs(col - queenCol[i]))
return false;
}
return true;
}
};