Leetcode---51. N 皇后---每日一题---DFS(回溯)---复习皇后问题

51. N 皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例：

输入： 4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”], ["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。

提示：

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

代码

class Solution { public: vector<vector<bool>> vis; void dfs(vector<vector<string>>& ans, vector<string>& tmp, int now, int n){ if(now == n) { ans.push_back(tmp); return; } string str; str.resize(n, '.'); for(int i = 0; i < n; i++){ // 分别记录正对角线，反对角线，列的访问情况 if(vis[0][now - i + n] || vis[1][now + i] || vis[2][i]) continue; // 符合条件，修改各参数 vis[0][now - i + n] = vis[1][now + i] = vis[2][i] = true; str[i] = 'Q'; tmp.push_back(str); // 进行搜索 dfs(ans, tmp, now + 1, n); // 搜索完毕，恢复各参数(回溯) vis[0][now - i + n] = vis[1][now + i] = vis[2][i] = false; str[i] = '.'; tmp.pop_back(); } } vector<vector<string>> solveNQueens(int n) { vis = vector<vector<bool>>(3, vector<bool>(2 * n, false)); vector<vector<string>> ans; vector<string> tmp; dfs(ans, tmp, 0, n); return ans; } };