当前位置: 首页 > news >正文

2. 皇后的控制力

题目描述:

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

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

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

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

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

测试输入期待的输出时间限制内存限制额外进程
测试用例 1以文本方式显示
  1. 2 1↵
以文本方式显示
  1. 4↵
1秒64M0
测试用例 2以文本方式显示
  1. 3 1↵
以文本方式显示
  1. 1↵
1秒64M0

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) {// 如果有任何空点没有被控制,则返回falsereturn false;}}}}// 所有空点都被控制,返回truereturn 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;
}

http://www.lryc.cn/news/261295.html

相关文章:

  • 南京邮电大学数据库实验二
  • 数据库 02-03 补充 SQL的子查询(where,from),子查询作为集合来比较some,exists,all(某一个,存在,所有)
  • 提升英语学习效率,尽在Eudic欧路词典 for Mac
  • 计算机网络英文总结
  • Spring上下文之注解模块ConfigurationMethod
  • 【深度学习】强化学习(三)强化学习的目标函数
  • Python高级算法——人工神经网络(Artificial Neural Network)
  • 深入理解JVM设计的精髓与独特之处
  • fastjson序列化与反序列化的忽略
  • 【TB作品】基于单片机的实验室管理系统,STM32,GM65二维码扫描模块
  • 超过 1450 个 pfSense 服务器因错误链而遭受 RCE 攻击
  • react面试总结2
  • hive 常见存储格式和应用场景
  • PyPDF2库对PDF实现读取的应用
  • C++ stack用法详解
  • QT案例 使用WMI获取win_32类的属性值,包括Win32提供程序类中的属性
  • TCP/UDP 的特点、区别及优缺点
  • 使用 Python 使用贝叶斯神经网络从理论到实践
  • Linux 中的网站服务管理
  • 阿里云cdn设置相同的域名路径访问不同的oss目录
  • 提示(Prompt)工程中提示词的开发优化基础概念学习总结
  • C#基础——语法学习
  • vue-实现高德地图-省级行政区地块显示+悬浮显示+标签显示
  • flutter ‘Gradle Libs‘ was added by build file ‘app/build.gradle‘
  • Java中的链式编程风格与应用案例
  • MTK Android P Sensor架构(一)
  • 低代码开发与传统软件开发:未来趋势与竞争格局
  • leetcode 股票问题全序列
  • SpringBoot中日志的使用log4j2
  • 机械设备企业网站建设的效果如何