皇后的控制力（C++语言）_python4皇后问题

题目描述：

我们对八皇后问题进行扩展。

国际象棋中的皇后非常神勇，一个皇后可以控制横、竖、斜线等4个方向（或者说是8个方向），只要有棋子落入她的势力范围，则必死无疑，所以对方的每个棋子都要小心地躲开皇后的势力范围，选择一个合适的位置放置。如果在棋盘上有两个皇后，则新皇后控制的势力范围与第一个皇后控制的势力范围可以进行叠加，这样随着皇后数量的增加，皇后们控制的范围越来越大，直至控制了棋盘中全部的格子。

现在我们关心的是，如果在 N×N 的棋盘上放入 M 个皇后（M个皇后相互之间不能冲突）控制棋盘中的格子，则共有多少种不同的放置方法？

输入：N (N <= 10)  M (M <= N)

输出：如果将 M 个皇后放入 N×N 的棋盘中可以控制全部棋盘中的格子，则不同的放置方法的数量

样例

输入（1）

2 1

输出（1）

4

输入（2）

3 1

输出（2）

1

代码

#include <iostream>
using namespace std;
 
int n, m, tot;
int *row, *column, *slash, *reslash;
 
int judge() {
    for (int i = 1; i <= n; i++) {
        if (row[i] == 999) {
            for (int j = 1; j <= n; j++) {
                if (column[j] == 999) {
                    if (!(reslash[i + j] == 1 || slash[n + i - j + 1] == 1)) {
                        return 0;
                    }
                }
            }
        }
    }
    return 1;
}
 
void traceback(bool flag, int level, int num) {
    if (level > n) {
        if (num != m) {
            return;
        }
        if (judge()) {
            tot++;
        }
        return;
    }
 
    if (n - level + num < m) {
        return;
    }
 
    if (!flag) {
        traceback(false, level + 1, num);
        traceback(true, level + 1, num + 1);
    } else {
        for (int i = 1; i <= n; i++) {
            if (column[i] == 999 && reslash[level + i] == 999 && slash[n + level - i + 1] == 999) {
                row[level] = level;
                column[i] = i;
                reslash[level + i] = 1;
                slash[n + level - i + 1] = 1;
                traceback(false, level + 1, num);
                traceback(true, level + 1, num + 1);
                row[level] = 999;
                column[i] = 999;
                reslash[level + i] = 999;
                slash[n + level - i + 1] = 999;
            }
        }
    }
}
 
int main() {
    cin >> n >> m;
    column = new int[n + 1];
    row = new int[n + 1];
    slash = new int[2 * n + 1];
    reslash = new int[2 * n + 1];
 
    for (int i = 0; i <= n; i++) {
        column[i] = row[i] = 999;
    }
 
    for (int i = 0; i < 2 * n + 1; i++) {
        slash[i] = reslash[i] = 999;
    }
 
    tot = 0;
    traceback(false, 1, 0);
    traceback(true, 1, 1);
    cout << tot << endl;
 
    delete[] column;
    delete[] row;
    delete[] slash;
    delete[] reslash;
 
    return 0;
}