- 总时间限制:
- 10000ms 内存限制:
- 65536kB
- 描述
- 在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。 输入
- 无输入。 输出
- 按给定顺序和格式输出所有八皇后问题的解（见Sample Output）。 样例输入
- 样例输出
-
No. 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 No. 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 No. 3 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 No. 4 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 No. 5 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 No. 6 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 No. 7 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 No. 8 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 No. 9 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 ...以下省略
==========================
首先本题坑点：结果要按列输出。
其次对于八皇后问题做个好几次了，其中复杂点的地方就是对角线的限制，但每次做都是用自己的方法写的，自己写的麻烦一点，所以这次翻了一下题解，学到了以规律代替数字条对角线的方法，而且这样也就没有“多指向”的问题了。
首先，还是附上按自己思路写的代码：
#include<bits/stdc++.h>
using namespace std;
int king[100][100]; //把数组开成整形，因为一个位置可能被多个位置所限制；
bool memor[100][100];
int k=0;
void signn(int x,int y)
{
king[x][y]++;
for(int i=1;i<=8;++i)
if(i!=x)king[i][y]++;
for(int i=x,j=y;i<=8&&j<=8;++i,++j)
if(i!=x&&j!=y)king[i][j]++;
for(int i=x,j=y;i>=1&&j>=1;--i,--j)
if(i!=x&&j!=y)king[i][j]++;
for(int i=x,j=y;i<=8&&j>=1;++i,--j)
if(i!=x&&j!=y)king[i][j]++;
for(int i=x,j=y;i>=1&&j<=8;--i,++j)
if(i!=x&&j!=y)king[i][j]++;
}
void f_signn(int x,int y)
{
king[x][y]--;
for(int i=1;i<=8;++i)
if(i!=x)king[i][y]--;
for(int i=x,j=y;i<=8&&j<=8;++i,++j)
if(i!=x&&j!=y)king[i][j]--;
for(int i=x,j=y;i>=1&&j>=1;--i,--j)
if(i!=x&&j!=y)king[i][j]--;
for(int i=x,j=y;i<=8&&j>=1;++i,--j)
if(i!=x&&j!=y)king[i][j]--;
for(int i=x,j=y;i>=1&&j<=8;--i,++j)
if(i!=x&&j!=y)king[i][j]--;
}
void printff() //本题坑点；
{
k++;
cout<<"No. "<<k<<endl;
for(int i=1;i<=8;++i)
{
for(int j=1;j<=8;++j)
cout<<memor[j][i]<<" ";
cout<<endl;
}
}
void search(int x)
{
if(x>8)
{
printff();
return ;
}
for(int i=1;i<=8;++i)
{
if(king[x][i]==0)
{
memor[x][i]=1;
signn(x,i);
search(x+1);
memor[x][i]=0;
f_signn(x,i);
}
}
}
int main()
{
search(1);
return 0;
}
然后，来看一下经典解法：
#include<bits/stdc++.h>
using namespace std;
bool d[101],b[101],c[101];//b标记该列，c标记对角线“/”方向,d标记“\”方向；
int k=0,a[101][101];
void search(int);
void printff();
int main()
{
search(1);
return 0;
}
void search(int i)
{
if(i>8)
{
printff();
return ;
}
for(int j=1;j<=8;++j)
if((!b[j])&&(!c[i+j])&&(!d[i-j+7]))
{
a[i][j]=1;
b[j]=1;
c[i+j]=1; //标记“/”方向；
d[i-j+7]=1; //标记“\”方向，另外+7是为了避免出现负数；
search(i+1);
b[j]=0;
c[i+j]=0;
d[i-j+7]=0;
a[i][j]=0;
}
}
void printff()
{
k++;
cout<<"No. "<<k<<endl;
for(int i=1;i<=8;++i)
{
for(int j=1;j<=8;++j)
{
cout<<a[j][i]<<" ";//按列输出；
}
cout<<endl;
}
}
The end;