Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Analysis:

Same idea just a little bit difference from the previous one.

Note:

If I use the vector as the data structure, the code cannot pass the large online judge, however, if I use the dynamic array, which successfully pass all the online judge test. What the hell? lol

Source Code:

class Solution { public: int res; bool isValid(int A[], int r){ for (int i=0;i<r;i++){ if ( (A[i]==A[r])||(abs(A[i]-A[r])==(r-i))){ return false; } } return true; } void nqueens(int A[], int cur, int n){ if (cur==n){ res++;return;} else{ for (int i=0;i<n;i++){ A[cur]=i; if (isValid(A,cur)){ nqueens(A,cur+1,n); } } } } int totalNQueens(int n) { // Start typing your C/C++ solution below // DO NOT write int main() function res=0; int *A = new int[n]; nqueens(A,0,n); return res; } };

Hi Yu, why it does not work if I use vector A(n, -1) instead of A[n]? Anything else is the same as yours but I can not still get AC on leetcode.

ReplyDeleteHi there, I'm also not sure why this situation happens, one reason might be that the memory of holding a vector is larger than the dynamic array?

DeleteHi Yu, I do not think that is the reason because in the previous Queens1 problem we can use vector. Why can't we do it this time? Maybe we should ask 1337. :)

DeleteHi Yu, the reason is you'd better use reference vector &A instead of vector A to avoid necessary vector copy. Then you just modify your code a little bit. Then good.

ReplyDelete