按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。
n 皇后問題 研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。
給你一個整數(shù) n ，返回所有不同的 n 皇后問題 的解決方案。
每一種解法包含一個不同的 n 皇后問題 的棋子放置方案，該方案中 ‘Q’ 和 ‘.’ 分別代表了皇后和空位。
示例 1：
輸入：n = 4
輸出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解釋：如上圖所示，4 皇后問題存在兩個不同的解法。
示例 2：
輸入：n = 1
輸出：[[“Q”]]
提示：
1 <= n <= 9
思路
N皇后問題是在一個NxN的棋盤上放置N個皇后，使得它們不能互相攻擊，即任何兩個皇后都不能處于同一行、同一列或同一斜線上。
定義一個位集（bitset）來記錄每一列以及兩個對角線上是否已經(jīng)放置了皇后。其中，vis1用于記錄列，vis2和vis3用于記錄兩個對角線。
在dfs函數(shù)中，首先檢查當(dāng)前搜索的深度是否已經(jīng)達(dá)到了棋盤的大小，如果達(dá)到了，說明已經(jīng)找到了一種放置皇后的方式，將其添加到結(jié)果集中。然后，遍歷當(dāng)前行的每一列，檢查放置皇后是否合法，即檢查當(dāng)前位置所在的列以及兩個對角線上是否已經(jīng)有皇后。如果合法，就在當(dāng)前位置放置皇后，并標(biāo)記當(dāng)前位置所在的列和兩個對角線，然后搜索下一行。搜索完后，需要進(jìn)行回溯，即恢復(fù)當(dāng)前位置的狀態(tài)，以便進(jìn)行下一次搜索。文章來源：http://www.zghlxwxcb.cn/news/detail-836148.html
AC代碼
/*
* @lc app=leetcode.cn id=51 lang=cpp
*
* [51] N 皇后
*/
// @lc code=start
class Solution {
static const int N = 15;
vector<vector<string>> ans;
vector<string> tmp;
bitset<N> vis1, vis2, vis3;
void dfs(int i, int n) {
// 遞歸出口
if (i == n) {
ans.push_back(tmp);
return;
}
for (int j = 0; j < n; j++) {
// 剪枝
if (vis1[j] || vis2[i + j] || vis3[n + i - j]) {
continue;
}
// 修改現(xiàn)場
vis1[j] = 1;
vis2[i + j] = 1;
vis3[n + i - j] = 1;
tmp[i][j] = 'Q';
dfs(i + 1, n);
// 恢復(fù)現(xiàn)場
vis1[j] = 0;
vis2[i + j] = 0;
vis3[n + i - j] = 0;
tmp[i][j] = '.';
}
}
public:
vector<vector<string>> solveNQueens(int n) {
// 初始化
vis1.reset();
vis2.reset();
vis3.reset();
tmp.resize(n);
for (auto &i : tmp) {
i.resize(n, '.');
}
dfs(0, n);
return ans;
}
};
// @lc code=end
文章來源地址http://www.zghlxwxcb.cn/news/detail-836148.html
到了這里，關(guān)于【力扣 51】N 皇后（回溯+剪枝+深度優(yōu)先搜索）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
