[蓝桥杯]试题 基础练习 2n皇后问题

#include<iostream>
#include<vector>
#include<cmath> 

using namespace std;

int chess[15][15] = {0}; 
int n = 0;
int res = 0;
bool check(int curR, int pos[])
{
	for(int i = 1; i < curR; i++)
	{
		if(pos[curR] == pos[i] || (abs(curR - i) == abs(pos[curR] - pos[i])))
		{
			return false;
		}
	}
	return true;
} 
void dfs2(int curR, int posB[], int posW[])
{//放白皇后
	if(curR == n+1)
	{
		res++;
		/*for(int i = 1; i <= n; i++)
		{
			cout<<posB[i]<<"---"<<posW[i]<< "   ";
		}
		cout<<endl;*/
		return ;
	}
	for(int i = 1; i <= n; i++)
	{
		if(posB[curR] == i)//不能和黑皇后放同一位置
			continue;
		if(chess[curR][i] == 0)
			continue;
		posW[curR] = i; //放白皇后
		if(check(curR, posW) == true)
		{
			dfs2(curR+1, posB, posW);
		}
	}
} 
void dfs1(int curR,int posB[], int posW[])
{//放黑皇后
	if(curR > n)
	{
		dfs2(1,posB, posW);
		return ;
	}
	for(int i = 1; i <= n; i++)
	{
		if(chess[curR][i] == 0)
			continue;
		posB[curR] = i;//放黑皇后
		if(check(curR, posB) == true)
		{
			dfs1(curR + 1, posB, posW);
		} 
	}
} 
int main()
{
	cin>>n;
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			cin>>chess[i][j];
		}
	}
	int posB[15] = {0};
	int posW[15] = {0};
	
	dfs1(1, posB, posW);
	cout<<res;
	return 0;
}