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:vector<vector<string>>solveNQueens(intn){// 记录多个答案vector<vector<string>>ans;// 记录单个答案vector<string>res;// 记录每层的答案strings(n,'.');// 某一列是否被标记vector<bool>st_col(n,false);// 主对角线是否被标记vector<bool>main_diag(n*2,false);// 次对角线是否被标记vector<bool>sub_diag(n*2,false);// 每层枚举一行的所有列dfs(0,n,st_col,main_diag,sub_diag,s,res,ans);returnans;}voiddfs(introw,intn,vector<bool>&st_col,vector<bool>&main_diag,vector<bool>&sub_diag,string&s,vector<string>&res,vector<vector<string>>&ans){if(res.size()==n){ans.push_back(res);return;}// 每层枚举一行的所有列for(intcol=0;col<n;++col){// 没有列、主副对角线冲突if(st_col[col]==false&&main_diag[row+col]==false&&sub_diag[col-row+n]==false){st_col[col]=true;main_diag[row+col]=true;sub_diag[col-row+n]=true;s[col]='Q';res.push_back(s);s[col]='.';// 提前复原, 下一层要用到dfs(row+1,n,st_col,main_diag,sub_diag,s,res,ans);st_col[col]=false;main_diag[row+col]=false;sub_diag[col-row+n]=false;res.pop_back();}}}};