2014年4月16日 星期三

[LeetCode] N-Queens II

Problem:
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
Solution:O(n^2)
public class Solution {
   public int totalNQueens(int n) {
      if(n<=0)
         return 0;
      boolean column[] = new boolean[n];
      boolean xcross[] = new boolean[2*n-1];
      boolean ycross[] = new boolean[2*n-1];
      return getOK(n, 0,column, xcross, ycross);
   }
    
   public int getOK(int n, int level,boolean column[], boolean xcross[], boolean ycross[]) {
      int count = 0;
      if (level == n || n == 1)
         return 1;
      for (int i = 0; i < n; i++) {
         int x = i+level;
         int y = level - i + n-1;
   
         if (column[i] || xcross[x] || ycross[y])
            continue;
   
         xcross[x] = true;
         ycross[y] = true;
         column[i] = true;
         count+= getOK(n, level + 1,column,xcross, ycross);
   
         xcross[x] = false;
         ycross[y] = false;
         column[i] = false;
       }
       return count;
   }   
}

沒有留言:

張貼留言