题目描述
题目链接:52. N-Queens II
The n-queens puzzle is the problem of placing
n
queens on ann x n
chessboard such that no two queens attack each other.Given an integer
n
, return the number of distinct solutions to the n-queens puzzle.
例子
例子 1
见官网例子。
Constraints
1 <= n <= 9
解题思路
思路和 [Leetcode]51. N-Queens(C++) 基本一样,只是不需要存储具体的解,只需要用一个整型存储解的数量,在找到解时将其加一即可。代码如下:
#include <string>
#include <unordered_set>
#include <vector>
class Solution {
public:
int totalNQueens(int n) {
int result = 0;
std::unordered_set<int> col_used;
std::unordered_set<int> diag1;
std::unordered_set<int> diag2;
dfs(0, n, col_used, diag1, diag2, result);
return result;
}
private:
void dfs(int row, int n, std::unordered_set<int>& col_used,
std::unordered_set<int>& diag1, std::unordered_set<int>& diag2,
int& result) {
if (row == n) {
result++;
return;
}
std::string curr_row(n, '.');
for (int col = 0; col < n; ++col) {
if (col_used.count(col) || diag1.count(col - row) ||
diag2.count(col + row))
continue;
curr_row[col] = 'Q';
col_used.insert(col);
diag1.insert(col - row);
diag2.insert(col + row);
dfs(row + 1, n, col_used, diag1, diag2, result);
col_used.erase(col);
diag1.erase(col - row);
diag2.erase(col + row);
}
}
};
- 时间复杂度:
O(n!)
- 空间复杂度:
O(n)
GitHub 代码同步地址: 52.NQueensIi.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions