aboutsummaryrefslogtreecommitdiff
path: root/other/n_queens2.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/n_queens2.cpp')
-rw-r--r--other/n_queens2.cpp35
1 files changed, 35 insertions, 0 deletions
diff --git a/other/n_queens2.cpp b/other/n_queens2.cpp
new file mode 100644
index 0000000..2af1bcd
--- /dev/null
+++ b/other/n_queens2.cpp
@@ -0,0 +1,35 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ int totalNQueens(int n) {
+ vector<bool> col(n, true);
+ vector<bool> anti(2 * n - 1, true);
+ vector<bool> main(2 * n - 1, true);
+ vector<int> row(n, 0);
+ int count = 0;
+ helper(0, row, col, main, anti, count);
+ return count;
+ }
+
+private:
+ void helper(int i, vector<int> &row, vector<bool> &col, vector<bool> &main,
+ vector<bool> &anti, int &count) {
+ if (i == row.size()) {
+ count++;
+ return;
+ }
+ for (int j = 0; j < col.size(); j++)
+ if (col[j] && main[i + j] && anti[i + col.size() - 1 - j]) {
+ row[i] = j;
+ col[j] = main[i + j] = anti[i + col.size() - 1 - j] = false;
+ helper(i + 1, row, col, main, anti, count);
+ col[j] = main[i + j] = anti[i + col.size() - 1 - j] = true;
+ }
+ }
+};
+
+int main() {
+ Solution obj;
+ cout << obj.totalNQueens(4);
+}