基本算法之搜索
总时间限制:
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
- #include<iostream>
- #include<cstdlib>
- #include<cstdio>
- #include<cstring>
- #include<string>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- #define up(i,l,r) for(int i=l;i<=r;++i)
- const int ma=1000;
- int tot=1;
- int a[ma],b[ma],w[ma],m[ma];
- int print()
- {
- cout<<"No."<<tot++<<endl;
- up(j,1,8){
- up(i,1,8){
- if(j==a[i])cout<<"1";
- else cout<<"0";
- }
- cout<<endl;
- }
- }
- int search(int j)
- {
- for(int i=1;i<=8;++i){
- if(b[i]==0&&m[i+j]==0&&w[i-j+7]==0){
- a[j]=i;b[i]=1;
- w[i-j+7]=1;m[i+j]=1;
- if(j==8)print();
- else
- search(j+1);
- b[i]=0;
- w[i-j+7]=0;m[i+j]=0;
- }
- }
- }
- int main()
- {
- search(1);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3424451.html