首页 > > 程序设计 > C/C++ >

蓝桥杯之2n皇后

2018-06-18 03:54:20来源：未知阅读 ()

问题： 给定一个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

样例输出

样例输入

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

样例输出

分析：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             else
44             {
45                 //黑皇后放完了，开始放白皇后；
46                 //白皇后放完的话就是一种方法结束 
47                 if(q==2)
48                 {
49                     dfs(0,3);
50                 }
51                 else
52                 {
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             else
61             {
62                 //黑皇后放完了，开始放白皇后；
63                 //白皇后放完的话就是一种方法结束 
64                 if(q==2)
65                 {
66                     dfs(0,3);
67                 }
68                 else
69                 {
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;
}