N皇后
递归遍历
主要是去除同行和同列
class Solution { public: vector<vector<string>> result; vector<int>path; //求绝对值 int abs(int a) { if (a < 0) return -a; else return a; } void backtraking(int n ,vector<bool> &used ,int deep) { //当深度大于n时返回 if(deep > n) return; //当路径为最大深度,找到路径存入 if(path.size() == n) { //将数字路径转换成字符串路径 vector<string> path_s; for(int i=0;i<n;i++) { string tmp ; for(int k=0;k<n;k++) tmp +='.';//建立n个. for(int j=0;j<n;j++) if(j==path[i]) tmp[j] = 'Q';//在应该放Q的位置放Q path_s.push_back(tmp);//转换好的字符串存入路径 } //存入结果 result.push_back(path_s); return; } //层次循环,找到每一行的点。 for(int i=0 ; i<n; i++) { if(used[i] == true) continue; //该点用过了,跳过。一个树枝的点只能用一次 pair<int,int> x(deep,i);//当前可能有效点 bool flag = true; //当前点,和path路径里面所有点依次对比 for(int j =0 ; j < path.size() ;j++) { pair<int,int> y(j,path[j]);//path之前加入的点 //检测当前点与之前路径点,是否在一列一行和对角线 if( abs(x.first - y.first)==0 || abs(x.second - y.second)==0 || abs(x.first - y.first) == abs(x.second - y.second) ) flag = false; } //检测是合格点,加入path if(flag == true) { //记录该点使用 used[i] = true; path.push_back(i); //递归,深度+1(找下一行) backtraking(n,used,deep+1); path.pop_back(); used[i] = false; } } return; } vector<vector<string>> solveNQueens(int n) { vector<bool> used(n,false); backtraking(n ,used,0); return result; } };