3

kedebug · kedebug · commit f55a27d396e7 · 2014-04-23T21:27:01.000+08:00
diff --git a/N-QueensII/N-QueensII.cpp b/N-QueensII/N-QueensII.cpp
@@ -1,27 +1,22 @@
 class Solution {
 public:
-    int queens;
-    int mask;
     int totalNQueens(int n) {
-        // Start typing your C/C++ solution below
-        // DO NOT write int main() function
-        
-        mask = (1 << n) - 1;
-        queens = 0;
-        totalNQueensHelper(0, 0, 0);
-        return queens;
+        int result = 0;
+        dfs(result, n, 0, 0, 0);
+        return result;
     }
     
-    void totalNQueensHelper(int col, int ld, int rd) {
-        if (col != mask) {
-            int valid_pos = mask & (~(col | ld | rd));
-            while (valid_pos) {
-                int p = valid_pos & (-valid_pos);
-                valid_pos -= p;
-                totalNQueensHelper(col + p, (ld + p) << 1, (rd + p) >> 1);
+    void dfs(int& result, int n, int col, int l, int r) {
+        int mask = (1 << n) - 1;
+        if (col == mask) {
+            result++;
+        } else {
+            int valid = mask & (~(col | l | r));
+            while (valid) {
+                int p = valid & (-valid);
+                valid -= p;
+                dfs(result, n, col + p, (l + p) << 1, (r + p) >> 1);
             }
         }
-        else
-            queens += 1;
     }
-};
+};
