2. 皇后的控制力

题目描述：

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

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

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

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

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

C++代码 

#include <iostream>
#include <vector>

using namespace std;

int totalSolutions = 0; // 用于记录不同的放置方法的数量

// 检查当前位置是否安全
bool isSafe(int row, int col, const vector<string>& board, int N) {
    // 检查列
    for (int i = 0; i < row; ++i) {
        if (board[i][col] == 'Q') {
            return false;
        }
    }

    // 检查左上对角线
    for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }

    // 检查右上对角线
    for (int i = row, j = col; i >= 0 && j < N; --i, ++j) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }

    return true;
}

bool checkControl(const vector<string>& board, int N) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (board[i][j] == '.') {
                // 检查当前空点是否被控制
                bool controlled = false;

                // 检查列
                for (int k = 0; k < N; ++k) {
                    if (board[k][j] == 'Q') {
                        controlled = true;
                        break;
                    }
                }

                // 检查行
                for (int k = 0; k < N; ++k) {
                    if (board[i][k] == 'Q') {
                        controlled = true;
                        break;
                    }
                }

                // 检查左上对角线
                for (int k = i, l = j; k >= 0 && l >= 0; --k, --l) {
                    if (board[k][l] == 'Q') {
                        controlled = true;
                        break;
                    }
                }

                // 检查右上对角线
                for (int k = i, l = j; k >= 0 && l < N; --k, ++l) {
                    if (board[k][l] == 'Q') {
                        controlled = true;
                        break;
                    }
                }

                // 检查左下对角线
                for (int k = i, l = j; k < N && l >= 0; ++k, --l) {
                    if (board[k][l] == 'Q') {
                        controlled = true;
                        break;
                    }
                }

                // 检查右下对角线
                for (int k = i, l = j; k < N && l < N; ++k, ++l) {
                    if (board[k][l] == 'Q') {
                        controlled = true;
                        break;
                    }
                }

                if (!controlled) {
                    // 如果有任何空点没有被控制，则返回false
                    return false;
                }
            }
        }
    }
    // 所有空点都被控制，返回true
    return true;
}

// 递归解决问题
void solveNQueensUtil(int row, int N, int M, vector<string>& board) {
    if (row == N) {
        if (M == 0 && checkControl(board, N)) {
            totalSolutions++; // 找到一个解决方案
        }
        return;
    }

    // 尝试在当前行的每一列放置皇后
    for (int i = 0; i < N; ++i) {
        if (isSafe(row, i, board, N)) {
            board[row][i] = 'Q'; // 放置皇后
            solveNQueensUtil(row + 1, N, M - 1, board); // 递归到下一行
            board[row][i] = '.'; // 回溯，移除皇后
        }
    }

    // 如果当前行不放置皇后，也递归到下一行
    solveNQueensUtil(row + 1, N, M, board);
}

// 解决N皇后问题
int solveNQueens(int N, int M) {
    vector<string> board(N, string(N, '.'));
    solveNQueensUtil(0, N, M, board);
    return totalSolutions;
}

int main() {
    int N, M;
    cin >> N >> M;
    cout <<  solveNQueens(N, M) << endl;
    return 0;
}