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;
}
}
没有评论:
发表评论