- 總時間限制:
- 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;