LeetCode 0051 - N-Queens
# Hints
- DFS
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
The n-queens puzzle is the problem of placing queens on an chessboard such that no two queens attack each other.
Given an integer , return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q'
and '.'
both indicate a queen and an empty space respectively.
Example:
Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
# 题意
给定一个正整数 ,求 皇后问题的所有合法解。
# 题解
N 皇后问题是 DFS 的经典问题。
在具体实现中,我们用 表示第 行的皇后的列编号,并在 DFS 时维护 数组,这样可以高效地检查当前方案的合法性。
# AC代码
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
// 初始化
int y[n];
vector<vector<string>> res;
// DFS
dfs(0, y, res, n);
// 返回
return res;
}
// 深度优先搜索
void dfs(int index, int y[], vector<vector<string>> & res, const int n) {
// 递归终止
if (index == n) {
// 绘制答案
vector<string> solution;
string row(n, '.');
for (int i = 0; i < n; i ++) {
row[y[i]] = 'Q';
solution.push_back(row);
row[y[i]] = '.';
}
// 更新答案
res.push_back(solution);
// 返回
return;
}
// 递归
for (int i = 0; i < n; i ++) {
y[index] = i;
if (is_legal(index, y)) {
dfs(index + 1, y, res, n);
}
}
}
// 判断是否合法
bool is_legal(int index, int y[]) {
// 遍历行
for (int i = 0; i < index; i ++) {
// 同列的情况
if (y[index] == y[i]) return false;
// 同对角线的情况
if (abs(index - i) == abs(y[index] - y[i])) return false;
}
// 返回
return true;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01