回溯法,以行为基准进行回溯,如果当前行列摆放皇后与之前的冲突,则不继续回溯,否则,继续下一行的回溯。
代码如下:
// // Created by jt on 2020/9/29. // #include <vector> using namespace std; class Solution { public: /** * * @param n int整型 * @return int整型 */ int totalNQueens(int n) { // write code here int res = 0; vector<int> vec; backtrack(vec, res, n); return res; } void backtrack(vector<int> &vec, int &res, int n) { if (vec.size() == n) { ++res; return; } for (int col = 0; col < n; ++col) { vec.push_back(col); if(!detectConflict(vec)) backtrack(vec, res, n); vec.pop_back(); } } bool detectConflict(vector<int> &vec) { int curRow = vec.size() - 1, curCol = vec[curRow]; for (int row = 0; row < curRow; ++row) { if (curCol == vec[row]) return true; if (curRow - row == abs(curCol - vec[row])) return true; } return false; } };