LeetCode 52. N-Queens II

上一题用了递归，这次用栈

```

class Solution { public: int ans=0; int a[100][100]; int m; int x[100005]; int y[100005]; int s[100005]; int p[100005]; int totalNQueens(int n) {

m=n; memset(a,0,sizeof(a)); int pos=0; s[pos]=0; x[pos]=-1; y[pos]=-1; p[pos]=-1; pos++; while(pos!=0) { int i=s[pos-1]; if(i==n) { ans++; }

if(p[pos-1]<=n-1&&i!=n) { p[pos-1]++; while(a[i][p[pos-1]]!=0) { p[pos-1]++; } if(p[pos-1]!=n){ a[i][p[pos-1]]=1; setLock(i,p[pos-1],2); s[pos]=i+1; x[pos]=i; y[pos]=p[pos-1]; p[pos]=-1; pos++; continue; } } if(pos==1) break; a[x[pos-1]][y[pos-1]]=0; setLock(x[pos-1],y[pos-1],-2); pos--; } return ans; } void setLock(int x,int y,int num) { for(int i=x+1;i<m;i++) { a[i][y]+=num; } int tag=1; for(int i=x+1;i<m;i++) { if(y+tag<m) a[i][y+tag]+=num; if(y-tag>=0) a[i][y-tag]+=num; tag++; } } };

```