LeetCode 0052 - N-Queens II
# 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 the number of distinct solutions to the n-queens puzzle.
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.
# 题意
给定一个正整数 ,求 皇后问题的合法解的个数。
# 题解
与 LeetCode 0051 基本相同,稍加修改即可。
# AC代码
class Solution {
public:
int totalNQueens(int n) {
// 初始化
int y[n];
int res = 0;
// DFS
dfs(0, y, res, n);
// 返回
return res;
}
// 深度优先搜索
void dfs(int index, int y[], int & res, const int n) {
// 递归终止
if (index == n) {
res ++;
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