1803: 2n皇后问题

Time Limit: 1 SecMemory Limit: 128 MB

Submit: 34Solved: 26

[Submit][Status][Web Board]

Description

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

Input

 输入的第一行为一个整数n，表示棋盘的大小。接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

Output

 输出一个整数，表示总共有多少种放法。

Sample Input

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

Sample Output

2

0

---

bfs经典。

递归，八皇后的进阶版。整了半天其实只是我太傻了。。。忽略了很多很重要的东西。

注意点：

1，不同皇后要用不同的数组

2，输入的时候是输入棋盘的数组

3，可以给每个皇后标上不同数字进行区分

最后感谢：八皇后（dfs+回溯） - geloutingyu - 博客园

蓝桥杯 2n皇后问题(精简）C语言 - Five—菜鸟级的博客 - CSDN博客

基础练习 2n皇后问题 - 简书

---

AC代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int MAXN=30;

int vis[3][MAXN]={0};

int visB[3][MAXN]={0};

int n,tot,pos[MAXN][MAXN];

void dfsW(int cur){//白皇后

if(cur==n)//搜索完了，即将输出

{

tot++;

}

else {//还未搜索完

for(int i=0;i<n;i++)

{

if(pos[cur][i]==1&&vis[0][i]==0&&vis[1][cur+i]==0&&vis[2][cur-i+n]==0)

{

pos[cur][i]=2;//放下皇后

vis[0][i]=1;//皇后位置,主对角线,辅对角线标记已经用过了

vis[1][cur+i]=1;

vis[2][cur-i+n]=1;

dfsW(cur+1);//马上放下一行的白黑后

vis[0][i]=0;//已经放置了皇后和不能放皇后的位置清空 (恢复)

vis[1][cur+i]=0;

vis[2][cur-i+n]=0;

pos[cur][i]=1;

}

}

}

}

void dfsB(int cur){//黑皇后

if(cur==n)//搜索完了，即将输出

{

dfsW(0);

}

else {//还未搜索完

for(int i=0;i<n;i++)

{

if(pos[cur][i]==1&&visB[0][i]==0&&visB[1][cur+i]==0&&visB[2][cur-i+n]==0)

//一行一行发皇后，故不需要判断行冲突

//判断一列主对角线和辅对角线有没有被占据

//格子中x+y(cur-i+n)为辅对角线，x-y(cur+i)为主对角线

{

pos[cur][i]=3;//放下皇后,白皇后和黑皇后不一样

visB[0][i]=1;//皇后位置,主对角线,辅对角线标记已经用过了

visB[1][cur+i]=1;

visB[2][cur-i+n]=1;

dfsB(cur+1);//马上放下一行的黑皇后

visB[0][i]=0;//已经放置了皇后和不能放皇后的位置清空 (恢复)

visB[1][cur+i]=0;

visB[2][cur-i+n]=0;

pos[cur][i]=1;

}

}

}

}

int main(){

while(cin>>n){

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

cin>>pos[i][j];

tot=0;

dfsB(0);

cout<<tot<<endl;

}

return 0;

}