2015年9月22日星期二

Leetcode 52 N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

Solution 1: Still DFS, use res[0] to store the result.
 public class Solution {  
   public int totalNQueens(int n) {  
     char[][] matrix=new char[n][n];  
     for (int i=0; i<n; i++) Arrays.fill(matrix[i],'.');  
     int[] res=new int[1];  
     dfs(matrix,0,n,res);  
     return res[0];  
   }  
   private void dfs(char[][] matrix, int row, int n, int[] res) {  
     if (row==n) res[0]++;  
     else {  
       for (int i=0; i<n; i++) {  
         if (validate(matrix,row,i,n)) {  
           matrix[row][i]='Q';  
           dfs(matrix,row+1,n,res);  
           matrix[row][i]='.';  
         }  
       }  
     }  
   }  
   private boolean validate(char[][] matrix, int i, int j, int n) {  
     for (int k=1; i-k>=0; k++)   
       if (matrix[i-k][j]=='Q') return false;  
     for (int k=1; i-k>=0 && j+k<n; k++)  
       if (matrix[i-k][j+k]=='Q') return false;  
     for (int k=1; i-k>=0 && j-k>=0; k++)  
       if (matrix[i-k][j-k]=='Q') return false;  
     return true;  
   }  
 }  

没有评论:

发表评论