LeetCode热题100 N 皇后

题目描述按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。示例 1输入n 4输出[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]解释如上图所示4 皇后问题存在两个不同的解法。示例 2输入n 1输出[[“Q”]]提示1 n 9思路1 进行dfs每层代表选取的行数层内只需要遍历列数。2 每个位置需要判断列、主对角线、副对角线是否重复行不需要判断因为dfs将层隔开了。3 主对角线和副对角线的表示可以用 x y 和 y - x 表示注意y - x可能是负数所以需要进行偏正为y - x n。代码classSolution{public:vectorvectorstringsolveNQueens(intn){// 记录多个答案vectorvectorstringans;// 记录单个答案vectorstringres;// 记录每层的答案strings(n,.);// 某一列是否被标记vectorboolst_col(n,false);// 主对角线是否被标记vectorboolmain_diag(n*2,false);// 次对角线是否被标记vectorboolsub_diag(n*2,false);// 每层枚举一行的所有列dfs(0,n,st_col,main_diag,sub_diag,s,res,ans);returnans;}voiddfs(introw,intn,vectorboolst_col,vectorboolmain_diag,vectorboolsub_diag,strings,vectorstringres,vectorvectorstringans){if(res.size()n){ans.push_back(res);return;}// 每层枚举一行的所有列for(intcol0;coln;col){// 没有列、主副对角线冲突if(st_col[col]falsemain_diag[rowcol]falsesub_diag[col-rown]false){st_col[col]true;main_diag[rowcol]true;sub_diag[col-rown]true;s[col]Q;res.push_back(s);s[col].;// 提前复原, 下一层要用到dfs(row1,n,st_col,main_diag,sub_diag,s,res,ans);st_col[col]false;main_diag[rowcol]false;sub_diag[col-rown]false;res.pop_back();}}}};