题目描述
思路是DFS。枚举每一行在哪一列放皇后。同时用三个变量分别存,哪些列已经放了皇后,还有哪些对角线已经放了皇后。对于对角线的判断,我们可以分为方向从左上到右下的对角线,和方向从右上到左下的对角线两种类型分别判断。从左上到右下的对角线,我们规定( 0 , n − 1 ) (0,n-1)(0,n−1)所在的对角线是0 00号,( 0 , n − 2 ) (0,n-2)(0,n−2)所在的对角线是1 11号,等等,那么对角线的号码k kk和上面某点的坐标( i , j ) (i,j)(i,j)满足j = i + n − 1 − k j=i+n-1-kj=i+n−1−k,所以k = i − j + n − 1 k=i-j+n-1k=i−j+n−1;从右上到左下的对角线,我们规定( 0 , 0 ) (0,0)(0,0)所在的对角线是0 00号,( 0 , 1 ) (0,1)(0,1)所在的对角线是1 11号,等等,那么对角线的号码k kk和上面某点的坐标( i , j ) (i,j)(i,j)满足j = − i + k j=-i+kj=−i+k,所以k = i + j k=i+jk=i+j。搜到第n + 1 n+1n+1行的时候说明找到了一个解,输出答案即可。代码如下:
方法一:
int P[n],
int cout=0;
void generateP(int index)//下标从1开始
{
if(index=n+1)
{
bool flag;
for(int i=0;i<n-1;i++)
{
for(int j=i+1);j<n;j++)
{
if (abs(i-j)==abs(P[i]-P[j]))
flag=false;
}
}
if(flag=true)
count++;
return;//一定要出去,递归不要忘记写return!!
}
for(int x=1;x<=n;i++)
{
if(hashTable[x]==false){
P[index]=x;//not P[x]=index;
hashTable[x]=true;
generateP(index+1);
hashTable[x]=false;
}
}
}
方法二://回溯现场
int count=0,P[n];
int hashTable[n];
void generateP(int index)
{
if(index=n+1)
{
count++;
return;
}
for(int x=1;x<=n;x++)//第x行
{
bool flag=true;
if(hashTable[x]==false)
{
for(int i=1;i<index;i++)//遍历之前的皇后,因此不是for(int i=1;i<x;i++)
if(abs(index-i)==abs(P[index]-P[i]))//列数差和行数差
{
flag=flase;
break;
}
if(flag==true)
{
hashTable[x]==true;
P[index]=x;
generateP(index+1);
hashTable[x]==false;
}
}
}
}
方法三:
//剪枝:bool判断不对直接回溯恢复现场,顺序1
const int N=20;//对角线一共有2*n-1条
int n;
char g[N][N];
bool col[N],dg[N],udg[N]//行列,对角线,反对角
void dfs(int u)//u为列数
{
if(u==n)//栈被填满
{
for(int i=0;i<n;i++) puts(g[i]);//why?
return;
}
for(int i=0;i<n;i++)//栈没被填满
{
if(!col[i]&&!dg[u+i]&&!udg[n-u+i])//对角线:y=x+b 反对角线:y=-x+b;下标不为负数因此加n
{
g[u][i]='Q';
col[i]=dg[u+i]=udg[n-u+i]=true;
dfs[u+1];//回溯是完全对称的
col[i]=dg[u+i]=udg[n-u+i]=false;
g[u][i]='.';
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j>n;j++)
g[i][j]='.';
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla