题目链接

https://www.dotcpp.com/oj/problem1460.html

题目大意

正方形棋盘，n个黑皇后，n个白皇后，同色皇后不能同行同列同对角线放置，问总共多少种放置方式。
与之类似的是“m皇后问题（链接中的链接中的链接有“八皇后问题”） ”
如果不会本题，可以先去看看“八皇后问题”再看看“m皇后问题”，最后看看本题。

解题思路

dfs，注意标记的置一与置零，即标志刷新。
我们的dfs，确定每行的黑皇后和白皇后的位置标志置一，再去dfs下一行，回溯的时候标志置零。
开始我思考是否要先dfs黑皇后的位置，再dfs白皇后的位置。发现可以实现，但是分开记录下放置黑白皇后的种数后，总种数是无法计算，或者通过关系公式计算出的，因此我舍弃了这种方式，决定在一个dfs中实现。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=100;
int n;
bool vis[N][N];
bool l_b[N],fu_b[N],zhu_b[N];
bool l_w[N],fu_w[N],zhu_w[N];
bool mp[N][N];
int cnt;
void dfs(int h){
    if(h==n){cnt++;return ;}
    for(int i=0;i<n;i++){//black
        if(zhu_b[h-i+n] || fu_b[h+i] || !mp[h][i] || l_b[i]) continue;
        zhu_b[h-i+n]=1,fu_b[h+i]=1,l_b[i]=1;
        vis[h][i]=1;
        for(int j=0;j<n;j++){//white
            if(zhu_w[h-j+n] || fu_w[h+j] || !mp[h][j] || l_w[j] || vis[h][j]) continue;
            zhu_w[h-j+n]=1,fu_w[h+j]=1,l_w[j]=1;
            dfs(h+1);
            zhu_w[h-j+n]=0,fu_w[h+j]=0,l_w[j]=0;
        }
        zhu_b[h-i+n]=0,fu_b[h+i]=0,l_b[i]=0;
        vis[h][i]=0;
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>mp[i][j];
    dfs(0);
    cout<<cnt;    
}

吐槽

难道蓝桥不给数据范围吗？？？！！！