[leedcode 52] N-Queens II
2937 ワード
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
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;
}
}