怎么查询网站开发公司,浙江众安建设集团有限公司网站,wordpress主题hestia,猴王水果竞猜网站建设题目描述#xff1a;
我们对八皇后问题进行扩展。
国际象棋中的皇后非常神勇#xff0c;一个皇后可以控制横、竖、斜线等4个方向#xff08;或者说是8个方向#xff09;#xff0c;只要有棋子落入她的势力范围#xff0c;则必死无疑#xff0c;所以对方的每个棋子都要…题目描述
我们对八皇后问题进行扩展。
国际象棋中的皇后非常神勇一个皇后可以控制横、竖、斜线等4个方向或者说是8个方向只要有棋子落入她的势力范围则必死无疑所以对方的每个棋子都要小心地躲开皇后的势力范围选择一个合适的位置放置。如果在棋盘上有两个皇后则新皇后控制的势力范围与第一个皇后控制的势力范围可以进行叠加这样随着皇后数量的增加皇后们控制的范围越来越大直至控制了棋盘中全部的格子。
现在我们关心的是如果在 N×N 的棋盘上放入 M 个皇后M个皇后相互之间不能冲突控制棋盘中的格子则共有多少种不同的放置方法
输入N (N 10) M (M N)
输出如果将 M 个皇后放入 N×N 的棋盘中可以控制全部棋盘中的格子则不同的放置方法的数量
测试输入期待的输出时间限制内存限制额外进程测试用例 1以文本方式显示 2 1↵以文本方式显示 4↵1秒64M0测试用例 2以文本方式显示 3 1↵以文本方式显示 1↵1秒64M0
C代码
#include iostream
#include vectorusing namespace std;int totalSolutions 0; // 用于记录不同的放置方法的数量// 检查当前位置是否安全
bool isSafe(int row, int col, const vectorstring 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 vectorstring 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) {// 如果有任何空点没有被控制则返回falsereturn false;}}}}// 所有空点都被控制返回truereturn true;
}// 递归解决问题
void solveNQueensUtil(int row, int N, int M, vectorstring 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) {vectorstring 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;
}
