欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥题目:B-27、2n皇后问题

程序员文章站 2022-06-12 20:54:34
...

蓝桥题目:B-27、2n皇后问题

#include <iostream>
#include <cmath>
#include <cstring>
#define MAX 13//棋盘最大范围 
#define queen 2//两种棋 

using namespace std;

int N;
int rst = 0;
bool map[MAX][MAX];
int ans[queen][MAX];

bool check(int row, int column, int chess){
	if(map[row][column] == 1){
		for(int i = 0; i < chess; ++i){
			if(ans[i][row] == column){
				return 0;
			}
		}
		for(int i = 0; i < row; ++i){
			if(ans[chess][i] == column){//判断同列
				return 0;
			}
			if(abs(i - row) == abs(ans[chess][i] - column)){//判断对角线
				return 0;
			}
		}
		return 1;//能放
	}else{
		return 0;//不能放
	}
}

void dfs(int row, int chess){
	if(row == N){
		if(chess == queen-1){
			rst++;
			cout << rst << endl; 
		}else{
			dfs(0, chess + 1);
		}
	}
	for(int column = 0; column < N; ++column){
		if(!check(row, column, chess)){ 
			continue;
		}else{
			ans[chess][row] = column;//记录每种棋在每几行的列数
			dfs(row+1, chess);
		}
	}
}

int main(){
	cin >> N;
	for(int i = 0; i < N; ++i){
		for(int j = 0; j < N; ++j){
			cin >> map[i][j];
		}
	}
	dfs(0, 0);//第0种棋的第0行开始 
	cout << rst; 
	return 0;
}