[leedcode 52] N-Queens II

2937 ワード

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

    // N-Queens, , , print 

    // :isvalid , i 

    //      A[] , 

    int res;

    int A[];

    public int totalNQueens(int n) {

        A=new int[n];

        nqueens(0,n);

        return res;

        

    }

    public void nqueens(int cur,int n){

        if(cur==n){

            res++;

        }else{

            for(int i=0;i<n;i++){

                A[cur]=i;

                if(isValid(cur)){

                   nqueens(cur+1,n); 

                }

            }

        }

    }

    public boolean isValid(int cur){

        for(int i=0;i<cur;i++){

            if(A[i]==A[cur]||Math.abs(A[i]-A[cur])==cur-i)

                return false;

        }

        return true;

    }

}