Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
Solution:O(n^2)
public class Solution { public int totalNQueens(int n) { if(n<=0) return 0; boolean column[] = new boolean[n]; boolean xcross[] = new boolean[2*n-1]; boolean ycross[] = new boolean[2*n-1]; return getOK(n, 0,column, xcross, ycross); } public int getOK(int n, int level,boolean column[], boolean xcross[], boolean ycross[]) { int count = 0; if (level == n || n == 1) return 1; for (int i = 0; i < n; i++) { int x = i+level; int y = level - i + n-1; if (column[i] || xcross[x] || ycross[y]) continue; xcross[x] = true; ycross[y] = true; column[i] = true; count+= getOK(n, level + 1,column,xcross, ycross);
xcross[x] = false;
ycross[y] = false;
column[i] = false;
}
return count;
}
}
沒有留言:
張貼留言