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++;
}
}


};

```

LeetCode 52. N-Queens II

原文：https://www.cnblogs.com/dacc123/p/11420245.html