力扣-回溯-51 N皇后

思路

在棋盘上放皇后在回溯方法的树上来说，深度就是每一行放的皇后，宽度就是for循环里遍历放皇后，还有个问题是需要判断当前位置是否允许放皇后

代码

class Solution {
public:vector< vector<string> > result;vector<string> path;// 在放第Qnum行， n列的皇后bool isPosAllow(vector<string> path, int Qnum, int n){for(int i = 0; i < path.size(); i++){for(int j = 0; j < path.size(); j++){if(path[i][j] == 'Q'){if(j == n || abs(i - Qnum) == abs(j - n)){return false;}}}}return true;}void backtracking(int Qnum, int n){if(Qnum == n){result.push_back(path);return;}for(int i = 0; i < path[Qnum].size(); i++){if(isPosAllow(path, Qnum, i)){path[Qnum][i] = 'Q';backtracking(Qnum+1, n);path[Qnum][i] = '.';}}}vector<vector<string>> solveNQueens(int n) {for(int i = 0;i < n;i++){string s;for(int j = 0; j < n;j++){s+='.';}path.push_back(s);}backtracking(0, n);return result;}
};