蓝桥杯之2n皇后

2018-01-26 08:09:40来源:cnblogs.com作者:boisduval人点击

分享

问题:     给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的

         两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法?n小于等于8。

输入格式

  输入的第一行为一个整数n,表示棋盘的大小。
  接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。

输出格式

  输出一个整数,表示总共有多少种放法。

样例输入

4
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

1 1 1 1 1

样例输出

2

样例输入

4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

0

 

 

分析:1.用一个二维数组构造出一个n*n的矩阵。

   2.逐行选择某个合适的坐标来放置所谓的黑或者白皇后(如果放了黑,下次就放白的)。

     3.接着步骤2,放另一种皇后。

 

步骤二和步骤三的实现:

 1 void dfs(int i,int q)//i是初始行  q指的是是否在某位置上放置皇后  2 { 3     for(int j=0;j<n;j++)  4     { 5         //不能放的或者已经放过的  6         if(s[i][j]==0||s[i][j]==2)//已经放过的是2  7         { 8             continue; 9         }10         int flag=1;//默认可以放 11         int y1=j-1;//左上角的黑皇后 12         int y2=j+1;//右上角的黑皇后 13         for(int l=i-1;l>=0;l--) 14         {15             //判断同一列、斜线上是否有相同皇后(同行肯定不会有:从上到下进行的) 16             //同一列17             if(s[l][j]==q)//判断同一列上是否有相同的皇后 18             {19                 flag=0;20                 break;21             }22             //斜线23             if(y1>=0&&s[l][y1]==q)//判断左对角线上是否有 24             {25                 flag=0;26                 break;27             }28             y1--;    29             if(y2<n&&s[l][y2]==q)30             {31                 flag=0;32                 break;33             }34             y2++;35         }36         if(flag)37         {38             s[i][j]=q;//放皇后 39             if(i<n-1)40             {41                 dfs(i+1,q);42             } 43             else44             {45                 //黑皇后放完了,开始放白皇后;46                 //白皇后放完的话就是一种方法结束 47                 if(q==2)48                 {49                     dfs(0,3);50                 }51                 else52                 {53                     count++;54                 }55             }56             s[i][j]=1;//复原开始下一次 57         }58     }59 }

现在用C来实现

(其实用啥都一样,我不是太会用C++)

 1 #include <stdio.h> 2 void dfs(int i,int q); 3 int s[13][13]; 4 int n,count=0; 5 int main(){ 6     scanf("%d",&n); 7     for(int i=0;i<n;i++) 8     { 9         for(int j=0;j<n;j++)10         {11             scanf("%d",&s[i][j]);//对矩阵赋值 12         }13     }14     dfs(0,2);//黑皇后 15     printf("%d",count);16     return 0;17 }18 void dfs(int i,int q)//i=0  q=2 19 {20     for(int j=0;j<n;j++) 21     {22         //不能放的或者已经放过的 23         if(s[i][j]==0||s[i][j]==2)//已经放过的是2 24         {25             continue;26         }27         int flag=1;//默认可以放 28         int y1=j-1;//左上角的黑皇后 29         int y2=j+1;//右上角的黑皇后 30         for(int l=i-1;l>=0;l--) 31         {32             //判断同一列、斜线上是否有相同皇后(同行肯定不会有:从上到下进行的) 33             //同一列34             if(s[l][j]==q)//判断同一列上是否有相同的皇后 35             {36                 flag=0;37                 break;38             }39             //斜线40             if(y1>=0&&s[l][y1]==q)//判断左对角线上是否有 41             {42                 flag=0;43                 break;44             }45             y1--;    46             if(y2<n&&s[l][y2]==q)47             {48                 flag=0;49                 break;50             }51             y2++;52         }53         if(flag)54         {55             s[i][j]=q;//放皇后 56             if(i<n-1)57             {58                 dfs(i+1,q);59             } 60             else61             {62                 //黑皇后放完了,开始放白皇后;63                 //白皇后放完的话就是一种方法结束 64                 if(q==2)65                 {66                     dfs(0,3);67                 }68                 else69                 {70                     count++;71                 }72             }73             s[i][j]=1;//复原开始下一次 74         }75     }76 }

下面是不正宗的C++

#include<iostream>using namespace std;int s[13][13];int n;int count=0;//计数 void dfs(int i,int q)//i=0  q=2 {    for(int j=0;j<n;j++)     {        //不能放的或者已经放过的         if(s[i][j]==0||s[i][j]==2)//已经放过的是2         {            continue;        }        int flag=1;//默认可以放         int y1=j-1;//左上角的黑皇后         int y2=j+1;//右上角的黑皇后         for(int l=i-1;l>=0;l--)         {            //判断同一列、斜线上是否有相同皇后(同行肯定不会有:从上到下进行的)             //同一列            if(s[l][j]==q)//判断同一列上是否有相同的皇后             {                flag=0;                break;            }            //斜线            if(y1>=0&&s[l][y1]==q)//判断左对角线上是否有             {                flag=0;                break;            }            y1--;                if(y2<n&&s[l][y2]==q)            {                flag=0;                break;            }            y2++;        }        if(flag)        {            s[i][j]=q;//放皇后             if(i<n-1)            {                dfs(i+1,q);            }             else            {                //黑皇后放完了,开始放白皇后;                //白皇后放完的话就是一种方法结束                 if(q==2)                {                    dfs(0,3);                }                else                {                    count++;                }            }            s[i][j]=1;//复原开始下一次         }    }}int main(){    cin>>n;//对n赋值     for(int i=0;i<n;i++)    {        for(int j=0;j<n;j++)        {            cin>>s[i][j];//对矩阵赋值         }    }    dfs(0,2);//黑皇后     cout<<count<<endl;    return 0;}

结尾了,,有什么不懂的私聊我,一起学习,一起进步。1186294207

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台