class Solution public vectorvectorintvec; int total = 0; bool checkint x int y for int i = 0; i vecsize; i++ if veci1 == y veci0 + veci1 == x + y veci0 - veci1 == x
在backtracking函数中,应该先判断当前行是否已经放置了n个皇后,如果是则说明已经找到了一种解法,需要将total加1并返回。另外,在递归调用backtracking函数时,应该传入startindex+1而不是startindex,因为startindex代表的是当前行,需要继续在下一行放置皇后。修改后的代码如下:
class Solution {
public:
vector<vector<int>> vec;
int total = 0;
bool check(int x, int y) {
for (int i = 0; i < vec.size(); i++) {
if (vec[i][1] == y || vec[i][0] + vec[i][1] == x + y || vec[i][0] - vec[i][1] == x - y) {
return false;
}
}
return true;
}
void backtracking(int k, int startindex) {
if (startindex == k) {
total++;
return;
}
for (int i = 0; i < k; i++) {
if (check(i, startindex)) {
vec.push_back({i, startindex});
backtracking(k, startindex + 1);
vec.pop_back();
}
}
}
int totalNQueens(int n) {
backtracking(n, 0);
return total;
}
};
``
原文地址: https://www.cveoy.top/t/topic/ilQT 著作权归作者所有。请勿转载和采集!