（蓝桥杯）基础练习 2n皇后问题

我们先学习下经典案例中的八皇后问题

接着学习2n皇后问题

问题描述

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

样例输出

样例输入

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

样例输出

认真学习了八皇后问题后这个题不是问题，只需要一个一个判断，把条件稍微改下即可。

话不多说，上代码

#include<iostream>#include<cstdio>

using namespace std;

int chess[8][8];//使用全局变量，不用考虑二维数组的传入 
int count=0;
int n;
//黑皇后的判断条件，多留心 
int notdanger(int row,int col)
{
    int flag1=0,flag2=0,flag3=0,flag4=0,flag5=0,flag6=0;
    //列
    for(int i=0;i<n;i++){
        if(chess[i][col]==2){
            flag1=1;
            break;
        }
    }
    //左上角
    for(int i=row,j=col;i>=0&&j>=0;i--,j--){
        if(chess[i][j]==2){
            flag2=1;
            break;
        }
    }
    //右上角
    for(int i=row,j=col;i>=0&&j<n;i--,j++){
        if(chess[i][j]==2){
            flag3=1;
            break;
        }
    }
    //右下角
    for(int i=row,j=col;i<n&&j<n;i++,j++){
        if(chess[i][j]==2){
            flag4=1;
            break;
        }
    }
    //左下角
    for(int i=row,j=col;i<n&&j>=0;i++,j--){
        if(chess[i][j]==2){
            flag5=1;
            break;
        }
    }
    //可不可以放 
    if(chess[row][col]==0){
        flag6=1;
    }
    if(flag1||flag2||flag3||flag4||flag5||flag6){
        return 0;
    }
    return 1;
}
//白皇后的判断条件，这里需要多留点心，一点儿写错都不行 
int bainotdanger(int row,int col)
{
    int flag1=0,flag2=0,flag3=0,flag4=0,flag5=0,flag6=0;
    //列
    for(int i=0;i<n;i++){
        if(chess[i][col]==3){
            flag1=1;
            break;
        }
    }
    //左上角
    for(int i=row,j=col;i>=0&&j>=0;i--,j--){
        if(chess[i][j]==3){
            flag2=1;
            break;
        }
    }
    //右上角
    for(int i=row,j=col;i>=0&&j<n;i--,j++){
        if(chess[i][j]==3){
            flag3=1;
            break;
        }
    }
    //右下角
    for(int i=row,j=col;i<n&&j<n;i++,j++){
        if(chess[i][j]==3){
            flag4=1;
            break;
        }
    }
    //左下角
    for(int i=row,j=col;i<n&&j>=0;i++,j--){
        if(chess[i][j]==3){
            flag5=1;
            break;
        }
    }
    //可不可以放
    if(chess[row][col]==0||chess[row][col]==2){
        flag6=1;
    }
    if(flag1||flag2||flag3||flag4||flag5||flag6){
        return 0;
    }
    return 1;
}

void baiQueen(int row)//判断白皇后 
{
    if(row==n){
        count++;
    }else{
        for(int i=0;i<n;i++){
            if(bainotdanger(row,i)){
                chess[row][i]=3;
                baiQueen(row+1);
                chess[row][i]=1;
            }
        }
    }
}

void HeiQueen(int row)//判断黑皇后 
{
    if(row==n){
        baiQueen(0);//黑皇后排好后，开始排白皇后 
    }else{
        for(int i=0;i<n;i++){
            if(notdanger(row,i)){
                chess[row][i]=2;
                HeiQueen(row+1);
                chess[row][i]=1;
            }
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&chess[i][j]);
        }
    }
    HeiQueen(0);
    printf("%d\n",count);
    return 0;
}

秒客网

（蓝桥杯）基础练习 2n皇后问题

相关文章