蓝桥杯--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
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0

分析：
与n皇后对比，这里多了一种颜色的皇后
而且地图格子有些是不能放置皇后的，因此用一个map二维数组存放地图

在深搜的过程中，每次深搜对某一行的皇后进行放置，放置好了则深搜下一行
因此不需要判断放置皇后的时候是否与上一次放置在同一行
同时用一个flag数组标志各个列，
因为不能同列，因此假设该行该列放置了皇后，则将其标志为不可放置
最后的条件是对角，放置该皇后是否会形成对角关系 ，
这里通过数学的等腰三角形关系，计算两个腰是否相等，
即要放置元素的该行与之前以放置好的各个行元素进行计算行差，
再计算要放置元素的列位置与之前放置好的各个行中对应的列进行计算列差
判断行差与列差是否相等。
循环比较的次数是n次，将要放置的第n行与之前的第0到n-1行计算行差列差计算
这里要注意计算的是两个皇后的不是一个

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

int map[10][10];
int N;
int flagA[10] = {0};//存储某一列是否已放置了皇后，用0和1 ，初值为0表示空 
int flagB[10] = {0};
int dirA[10],dirB[10];//存储从0到7行皇后的位置，初始化为-1 
int count ;

bool judge( int numA,int numB)
{
for ( int i = 0 ; i < numA ; i++)
    {
cout<<"此时numA = "<<numA<<" i="<<i<<" dirA[numA]="<<dirA[numA]<<" dirA[i]="<<dirA[i]<<endl;
if ( abs(numA-i) == abs(dirA[numA]-dirA[i]) )
return false;
    }
for ( int i = 0 ; i < numB ; i++)
    {
if ( abs(numB-i) == abs(dirB[numB]-dirB[i]) )
return false;
    }
return true;
}

bool judge( int num ,int numA,int numB)
{
for ( int i = 0 ; i < num ; i++)
    {
// cout<<"此时numA = "<<numA<<" i="<<i<<" dirA[numA]="<<dirA[numA]<<" dirA[i]="<<dirA[i]<<endl;
if ( abs(num-i) == abs(numA-dirA[i]) )
return false;
if ( abs(num-i) == abs(numB-dirB[i]) )
return false;
    }

return true;
}

void dfs(int num)
{
// cout<<"num == "<<num<<endl;
//从最后一行倒数往前排列皇后
if ( num == N )
    {
        ++count;
return;
    }

//2N皇后的在同一行
for ( int i = 0 ; i < N ; i++)
    {
for ( int j = 0 ; j < N ; j++)
        {
if ( j==i )continue;//白和黑不能在同一格子
//必须安置好白和黑才可以开始深搜下一行
//条件为放置皇后的点必须为可以放。然后再判断是否同列和对角
else if (map[num][i] && map[num][j] && !flagA[i]&& !flagB[j]&&judge(num,i,j))
            {

                flagA[i] = flagB[j] = 1;
                dirA[num] = i;
                dirB[num] = j;
                dfs(num+1);
                flagA[i] = flagB[j] = 0;
                dirA[num] = -1;
                dirB[num] = -1;
            }
        }
    }

}

int main ()
{
cin>>N;

for ( int i = 0 ; i < N ; i++)
for ( int j = 0 ; j < N ; j++)
cin>>map[i][j];
//map[i][j] = 1;
/*
 cout<<"地图为"<<endl;

 for ( int i = 0 ; i < N ; i++)
 {
 for ( int j = 0 ; j < N ; j++)
 cout<<map[i][j]<<' ';
 cout<<endl;
 }
*/

memset(dirA,-1,sizeof(dirA));
memset(dirB,-1,sizeof(dirB));

    count = 0 ;

    dfs(0);

cout<<count<<endl;

return 0;
}