n皇后问题的简单变式

思路：

其实就是进行两次n皇后问题的填充
第一次先摆放白皇后（黑皇后也行）
如果白皇后能全部摆完，则继续摆放黑皇后（或者白皇后）
直到全部摆放完，或者无法摆放为止
要注意的是，摆放一个皇后以后要记得将当前位置更新为不可以摆放

#include<iostream>

using namespace std;

const int N = 15;
int n;
int g[N][N];
bool col_1[N], dg_1[N], udg_1[N];
bool col_2[N], dg_2[N], udg_2[N];
int res;

// 摆放黑皇后
void dfs_1(int u) {
    if (u == n) {
        res ++;
        return;
    }
    for (int i = 0; i < n; i ++) {
        if (!col_1[i] && !dg_1[i - u + n] && !udg_1[i + u] && g[u][i] == 1) {
            col_1[i] = dg_1[i - u + n] = udg_1[i + u] = true;
            g[u][i] = 0;
            dfs_1(u + 1);
            col_1[i] = dg_1[i - u + n] = udg_1[i + u] = false;
            g[u][i] = 1;
        }
    }
}

// 摆放白皇后
void dfs_2(int u) {
    if (u == n) {
        dfs_1(0);
    }
    for (int i = 0; i < n; i ++) {
        if (!col_2[i] && !dg_2[i - u + n] && !udg_2[i + u] && g[u][i] == 1) {
            col_2[i] = dg_2[i - u + n] = udg_2[i + u] = true;
            g[u][i] = 0;
            dfs_2(u + 1);
            col_2[i] = dg_2[i - u + n] = udg_2[i + u] = false;
            g[u][i] = 1;
        }
    }
}

int main() {

    cin >> n;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            cin >> g[i][j];
        }
    }

    dfs_2(0);

    cout << res << endl;

    return 0;
}