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

蓝桥杯 - 受伤的皇后

解题思路:

递归 + 回溯(n皇后问题的变种)

在 N 皇后问题的解决方案中,我们是从棋盘的顶部向底部逐行放置皇后的,这意味着在任何给定时间,所有未来的行(即当前行之下的所有行)都还没有被探查或放置任何皇后。因此,检查下方行是没有意义的,因为它们总是空的。所以只需要检查左上45°和右上45°。

import java.util.Scanner;public class Main {static int count = 0;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int[][] arr = new int[n][n];dfs(arr, 0);System.out.println(count);}public static void dfs(int[][] arr, int row) {if (row == arr.length) {count++;return;}// 遍历列,因为n行n列,所以arr.length和arr[0].length是一样的for (int j = 0; j < arr.length; j++) {if (checkValid(arr, row, j)) {arr[row][j] = 1;dfs(arr, row + 1);// 回溯arr[row][j] = 0;}}}public static boolean checkValid(int[][] arr, int row, int col) {// 检查列,因为n行n列,所以row既是行的长度又是列的长度for (int i = 0; i < row; i++) {if (arr[i][col] == 1) {return false;}}// 检查左上45°for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (arr[i][j] == 1 && Math.abs(row - i) < 3) {return false;}}// 检查右上45°for (int i = row - 1, j = col + 1; i >= 0 && j < arr.length; i--, j++) {if (arr[i][j] == 1 && Math.abs(row - i) < 3) {return false;}}return true;}
}

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

相关文章:

  • AcWing---乌龟棋---线性dp
  • python代码使用过程中使用快捷键注释时报错
  • go之web框架gin
  • SpringBoot 定时任务实践、定时任务按指定时间执行
  • MYSQL数据库故障排除与优化
  • 算法-数论-蓝桥杯
  • 222.完全二叉树节点个数
  • C++中的string类操作详解
  • Java绘图坐标体系
  • 【MATLAB源码-第38期】基于OFDM的块状导频和梳状导频误码率性能对比,以及LS/LMMSE两种信道估计方法以及不同调制方式对比。
  • javaWeb车辆管理系统设计与实现
  • 【DM8】间隔分区
  • 0基础如何进入IT行业?
  • C#将Console写至文件,且文件固定最大长度
  • 《CSS 知识点》仅在文本有省略号时添加 tip 信息
  • 彩虹聚合DNS管理系统v1.0全新发布
  • 3.10 Python数据类型转换
  • Kotlin基础学习
  • 配置交换机 SSH 管理和端口安全——实验1:配置交换机基本安全和 SSH管理
  • 海山数据库(He3DB)原理剖析:浅析Doris跨源分析能力
  • 第十三届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组 题解
  • 20240324-1-集成学习面试题EnsembleLearning
  • 默克尔(Merkle)树 - 原理及用途
  • 设计模式:迭代器模式
  • Navicat Premium 16常用快捷键
  • LeetCode笔记——1042.不邻接植花
  • Centos7搭建 Skywalking 单机版
  • 定制您的设备体验:如何更改Android启动动画
  • Docker日常系列
  • Midjourney该怎么用?从零基础到落地实践