##题目
####N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
##解题思路
该题和N-Queens基本相同，只是最后返回的是解得个数。但是这里需要注意的是:用java写的时候，基本数据类型是值传递，因此不能用int来作为递归的结果参数。
##算法代码
代码采用JAVA实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
public class {
public int totalNQueens(int n) {
ArrayList<Integer> res = new ArrayList<Integer>();
res.add(0);
helper(n,0,new int[n],res);
return res.get(0);
}
void helper(int n,int row,int[] columnForRow, ArrayList<Integer> res)
{
if(row==n)
{
int num=res.get(0)+1;
res.set(0,num);
return;
}else{
for(int i=0;i<n;i++)
{
columnForRow[row]=i;
if(check(row,columnForRow))
{
helper(n,row+1,columnForRow,res);
}
}
}
}
boolean check(int row,int[] columnForRow)
{
for(int i=0;i<row;i++)
{
if(columnForRow[row]==columnForRow[i] || Math.abs(columnForRow[row]-columnForRow[i])==(row-i))
return false;
}
return true;
}
}
|
近期评论