2n皇后问题

基础练习 2n皇后问题   时间限制：1.0s   内存限制：512.0MB         问题描述 　　给定一个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

 

#include <iostream> #include <cmath> #include <cstdlib> #include <cstring> #define Max 8 using namespace std; int x; int wqueen[Max]; int bqueen[Max]; int map[Max][Max]; int count = 0; int place(int k); int wqueue(int k); int bqueue(int k); int main() { cin>>x; for(int i = 0; i < x; i++) for(int j = 0; j < x; j++) cin>>map[i][j]; memset(wqueen,-1,sizeof(int)*x); memset(bqueen,-1,sizeof(int)*x); wqueue(0); cout<<count<<endl; } int wqueue(int k) { int i,j; //bool b = true; for( j = 0; j < x; j++) { //b = true; if(map[k][j]) wqueen[k] = j; else continue; for( i = 0; i < k; i++) { if(wqueen[i]==wqueen[k]||fabs(i-k)==fabs(wqueen[i] - wqueen[k])) { wqueen[k] = -1; break; } } if(wqueen[k] == j) if(k < x-1) wqueue(k+1); else if(k==x- 1) bqueue(0); } } int bqueue(int k) { int i,j; // bool b = true; for( i = 0; i < x; i++) { ///b = true; if(map[k][i]&&wqueen[k]!=i) bqueen[k] = i; else continue; for( j = 0; j < k; j++) { if(bqueen[j]==bqueen[k]||fabs(j-k)==fabs(bqueen[j] - bqueen[k])) { // b = false; bqueen[k] = -1; break; } } if(bqueen[k] == i) if(k < x-1) bqueue(k+1); else if(k == x-1) { count++; break; // b = false; } } }

注释部分可以不看是我调试用的

然后，关于一个函数提出来说一下：

menset：

void *memset(void *s, int ch,  size_t n); 函数解释：将s中当前位置后面的n个字节 （typedef unsigned int size_t ）用 ch 替换并返回 s 。 memset：作用是在一段内存块中填充某个给定的值，它是对较大的 结构体或 数组进行清零操作的一种最快方法

在string.h或者cstring头文件中