N-Queens II
还是n皇后问题, 这次问有几种解法, 这次变成了一个组合问题, 因为每个地方都可以放不同的皇后, 所以我们用一个数组记录重复的元素.
|
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 |
public class Solution { int res = 0; public int totalNQueens(int n) { if (n <= 0) return 0; int [] loc = new int[n]; dfs(loc,0,n); return res; } public void dfs(int[] loc, int cur, int n) { if (cur == n) { res += 1; return; } for (int i = 0 ; i < n; i++) { loc[cur] = i; if(isValid(loc,cur)) { dfs(loc, cur+1, n); } } } public boolean isValid(int[] loc, int cur){ for(int i=0;i<cur;i++){ if(loc[i]==loc[cur]||Math.abs(loc[i]-loc[cur])==(cur-i)) return false; } return true; } } |