信息学奥赛一本通T1213：搜索与回溯算法（DFS） 八皇后问题

【题目描述】在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。【输入】(无)【输出】按给定顺序和格式输出所有八皇后问题的解（见样例）。【输入样例】(无)【输出样例】No. 1【源程序】 

信息学奥赛一本通T1213：八皇后问题

【题目描述】

在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。

【输入】

(无)

【输出】

按给定顺序和格式输出所有八皇后问题的解（见样例）。

【输入样例】

(无)

【输出样例】

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<cstdio>
#include<cstdlib>
#include<cstring>
#define N 100
using namespace std;
int a[N][N],b[N];
int vis[N][N];
int tot;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int step)
{
    if(step==8+1)
    {
        tot++;
        for(int i=1;i<=8;i++)
            a[tot][i]=b[i];
        return;
    }
    for(int i=1;i<=8;i++)
    {
        if(vis[0][i]==0&&vis[1][step+i]==0&&vis[2][step-i+8]==0)
        {
            vis[0][i]=1;
            vis[1][i+step]=1;
            vis[2][step-i+8]=1;
            b[step]=i;
            dfs(step+1);
            vis[0][i]=0;
            vis[1][i+step]=0;
            vis[2][step-i+8]=0;
        }
    }
}
int main()
{
    dfs(1);
    for(int t=1;t<=tot;t++)
    {
        printf("No. %d\n",t);
        for(int i=1;i<=8;i++)
        {
            for(int j=1;j<=8;j++)
            {
                if(a[t][j]==i)
                    cout<<"1 ";
                else
                    cout<<"0 ";
            }
            cout<<endl;
        }
    }
    return 0;
}

 

信息学奥赛一本通T1213：搜索与回溯算法（DFS） 八皇后问题 归属于 搜索与回溯算法（DFS），更多同类题解源程序见：搜索与回溯算法（DFS） 和 八皇后问题

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章

轩爸

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！