【大神来看这里！】N后问题非递归算法 跪求时间复杂度

#include<iostream>
using namespace std;
void display(int **aa,int n)
{
cout<<"----------------------------------------------------"<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<aa[i][j]<<" ";
}
cout<<endl;
}
cout<<"----------------------------------------------------"<<endl;
}
void main()
{
/////程序开始
int n;
cout<<"请输入皇后个数N"<<endl;
cin>>n;
while(n<4)
{
cout<<"请重新输入，皇后个数过少:";
cin>>n;
}
///////生成棋盘，动态分配二维数组，初始化为0
int **aa;
aa=new int *[n];
for(int i=0;i<n;i++)
aa[i]=new int[n];
for(i=0;i<n;i++)
for(int j=0;j<n;j++)
aa[i][j]=0;
//////
int x=0,y=0;//定位当前行与当前列,初始化为第一行第一列
int *col=new int[n];//标记n列中哪一列不能放皇后，即这一列已经有皇后.0 能放 1不能放
int *a=new int[2*n-1];//标记左下到右上的n+1个斜方向能不能放皇后，0 能放 1不能放
int *b=new int[2*n-1];//标记左上到右下的n+1个斜方向能不能放皇后，0 能放 1不能放
for(i=0;i<2*n-1;i++)//初始化标记
{
a[i]=b[i]=0;
if(i<n)
col[i]=0;
}
bool available=1;//判断(x,y)这个位置能不能放皇后，1能放，0不能
int count=0;//记录解的个数
while(1)
{
if(col[y]==0&&a[x+y]==0&&b[x-y+n-1]==0) available=1;
else available=0;
if(available)
{
aa[x][y]=1;//放一个皇后
col[y]=1;a[x+y]=1;b[x-y+n-1]=1;//标记列与斜方向不能放皇后了
//display(aa,n);
if(x==n-1) {display(aa,n);count++;}//是最后一行，一个解产生
else
{
x++;//当前行设为下一行
y=0;//当前列变为当前行的第一个位置
continue;
}
if(x==n-1&&y!=n-1)
{
aa[x][y]=0,col[y]=0,a[x+y]=0,b[x-y+n-1]=0;//释放该皇后所控制的方向
y++;
continue;
}
if(x==n-1&&y==n-1)
{//回溯之前
aa[x][y]=0,col[y]=0,a[x+y]=0,b[x-y+n-1]=0;//释放该皇后所控制的方向
bool t=1;//回溯到上一行了，对下一个待测位置的列进行定位，释放该行皇后控制的方向
while(t)//回溯到上一行，要确定这一行的皇后不是最后一个位置，否则回溯的没有意义，
//还要继续回溯；如果皇后在最后一列，则再回一行，直到皇后不在最后一列，并且要保证回溯到第一行时，处理？？
{
t=0;
x--;
if(x==-1) {getchar(); cout<<"总的解为"<<count<<"种 "<<endl;getchar();exit(1);}
for(int l=0;l<n;l++)
if(aa[x][l]==1)
{
if(l==n-1)
t=1;//如果该行皇后在最后一个，继续while循环，向上回溯
else
{t=0;y=l+1;}//如果该行皇后不是最后一个，停止回溯，退出while循环
//无论该行皇后在该行最后一个位置与否，都要释放皇后控制的方向
aa[x][l]=0;
col[l]=0,a[x+l]=0,b[x-l+n-1]=0;
break;
}
}
}
}
else
{
if(y!=n-1) y++;
else//回溯
{
if(x==0) break;//是第一行，算法结束
else
{//清空当前行及以下各行棋盘，当前行设为上一行，当前列设为当前行的下一个待测位置
bool t=1;
while(t)
{
t=0;
x--;
if(x==-1) {getchar(); cout<<"总的解为"<<count<<"种 "<<endl;getchar();exit(1);}
for(int l=0;l<n;l++)
if(aa[x][l]==1)
{
if(l==n-1)
t=1;//如果该行皇后在最后一个
else
{t=0;y=l+1;}//如果该行皇后不是最后一个，继续while循环，向上回溯
//无论该行皇后在该行最后一个位置与否，都要释放皇后控制的方向
aa[x][l]=0;
col[l]=0,a[x+l]=0,b[x-l+n-1]=0;
break;
//cout<<"释放的方向5:"<<x+l<<endl;
}
}
}
}
}
}
//////
delete[]a;
delete[]b;
delete []aa;
}