n-皇后-dfs


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {
    static int n,N = 20;    //这里只会用到2 * n - 1的格子,开大点保险
    static char[][] g = new char[N][N];
    static boolean[] col = new boolean[N];  //col[i]表示当前行的第i列是否被用过,
    static boolean[] dg = new boolean[N];   //dg[i]表示第i个主对角线是否用过,主对角线是[0][0]~[N][N]方向
    static boolean[] udg = new boolean[N];  //表示同上,反对角线是[0][N]~[N][0]那条对角线
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args)throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = '.';
            }
        }

        dfs(0);
        out.flush();
    }

    public static void dfs(int u)throws IOException {
        //只有n个数都放进去了才会打印,如果只放了n - 1个数就回溯的话,这个方案就表示行不通
        if (u == n){
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    out.write(g[i][j] + "");
                }
                out.newLine();
            }
            out.newLine();
            return;
        }

        //每次再往前走的时候,发现这个点不能用就不管这个点,去判断下一个点
        for (int i = 0; i < n; i++) {
            //g[u][i]没被用过,且该点的主反对角线也没被用过
            if (!col[i] && !dg[u - i + n] && !udg[i + u]){
                /*
                所有下标都从0开始
                主对角线上的的表达式为u = i + b,其中行-列的值为定值
                每一个b对应一条副对角线 b ∈[-(N - 1),N - 1],一共 2 * N - 1个取值
                这里的u - i 或者 i - u都没事,不影响

                副对角线的表达式为 u = -i + b,其中行 + 列为定值
                每一个b对应一条副对角线 b ∈[0,2 * (N - 1)],一共 2 * N - 1个取值
                 */
                //没用过的点把皇后放进去
                g[u][i] = 'Q';
                //把该点的主副对角线标记为用过
                col[i] = dg[u - i + n] = udg[i + u] = true;

                //找下一行的放皇后的位置
                dfs(u + 1);

                //一条路走完往回归的时候记得要把走过的路恢复,不然下次走会有误
                col[i] = dg[u - i + n] = udg[i + u] = false;
                g[u][i] = '.';
            }
        }

    }

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/359577.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Makefile编译原理 makefile中的include关键字

一.makefile中的include关键字 类似C语言中的include 将其他文件的内容原封不动的搬入当前文件 make对include关键字的处理方式&#xff1a; 在当前目录搜索或指定目录搜索目标文件 搜索成功&#xff1a;将文件内容搬入当前makefile中 搜索失败&#xff1a;产生警告&…

聚观早报 | 360 AI搜索App上线;岚图汽车与京东达成合作

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 1月30日消息 360 AI搜索App上线 岚图汽车与京东达成合作 三星电子在硅谷新设实验室 小米平板7系列参数曝光 Spa…

大创项目推荐 题目:基于深度学习的中文对话问答机器人

文章目录 0 简介1 项目架构2 项目的主要过程2.1 数据清洗、预处理2.2 分桶2.3 训练 3 项目的整体结构4 重要的API4.1 LSTM cells部分&#xff1a;4.2 损失函数&#xff1a;4.3 搭建seq2seq框架&#xff1a;4.4 测试部分&#xff1a;4.5 评价NLP测试效果&#xff1a;4.6 梯度截断…

代码随想录算法刷题训练营day20

代码随想录算法刷题训练营day20&#xff1a;LeetCode(654)最大二叉树、LeetCode(617)合并二叉树、LeetCode(700)二叉搜索树中的搜索、LeetCode(700)二叉搜索树中的搜索、LeetCode(98)验证二叉搜索 LeetCode(654)最大二叉树 题目 代码 import java.util.Arrays;/*** Definit…

MATLAB有限元应用-四边形八节点梁受力弯曲

MATLAB在处理平面有限元问题和梁弯曲问题上有很强的能力,主要体现在以下几个方面: 建模与网格划分 MATLAB内置了方便的图形界面工具(pdetoolbox等),可以快速对几何模型进行二维三维网格划分,生成有限元分析需要的网格。 求解器 MATLAB内置了多种求解偏微分方程的有限元求解器…

大模型重塑车载语音交互:赛道巨头如何引领新周期?

车载语音交互赛道正进入新一轮竞争周期。 高工智能汽车注意到&#xff0c;传统车载语音交互赛道当前基本已进入成熟期&#xff0c;主要为任务型助手&#xff0c;包括从单轮对话到多轮对话&#xff0c;单音区到多音区&#xff0c;从单一的导航、多媒体娱乐等座舱功能扩展智能驾…

钢材表面缺陷YOLOV8,OPENCV调用

【免费】钢材表面缺陷YOLOV8资源-CSDN文库 钢材表面缺陷YOLOV8NANO&#xff0c;训练得到PT模型&#xff0c;然后转换成ONNX&#xff0c;OPENCV的DNN调用&#xff0c;支持C,PYTHON,ANDROID

VScode中使用Xdebug调试PHP

君衍. 一、下载VScode与PHPstudy二、配置PHP环境变量三、PHPstudy中启用xdebug扩展四、打开php.ini&#xff0c;修改配置五、修改vscode配置六、VScode安装相关插件七、配置launch.json八、设置断点&#xff0c;开始调试 一、下载VScode与PHPstudy 首先我们自然是需要搭建环境…

C++ 数论相关题目 博弈论 Nim游戏

给定 n 堆石子&#xff0c;两位玩家轮流操作&#xff0c;每次操作可以从任意一堆石子中拿走任意数量的石子&#xff08;可以拿完&#xff0c;但不能不拿&#xff09;&#xff0c;最后无法进行操作的人视为失败。 问如果两人都采用最优策略&#xff0c;先手是否必胜。 输入格式…

《统计学习方法:李航》笔记 从原理到实现(基于python)-- 第5章 决策树(代码python实践)

文章目录 第5章 决策树—python 实践书上题目5.1利用ID3算法生成决策树&#xff0c;例5.3scikit-learn实例 《统计学习方法&#xff1a;李航》笔记 从原理到实现&#xff08;基于python&#xff09;-- 第5章 决策树 第5章 决策树—python 实践 import numpy as np import pand…

Docusaurus 文档侧边栏增加 New 标识

在使用 Docusaurus 搭建文档站点的时候&#xff0c;我们经常要给某个侧边栏菜单增加一些醒目的标识&#xff0c;比如针对新创建的文档给它一个 New 的标识&#xff0c; 以提醒过来看文档的用户这是一个新增加项或者新特性&#xff08;阅读的时候不要遗漏&#xff09;。 然而这个…

C#: form 添加窗体最小化事件,添加系统托盘图标,点击后可以打开、最小软件窗口

说明&#xff1a; 1.实现窗体在最小化后触发一个事件&#xff0c;可以去实现需要的功能。 2.最小化后软件图标出现在系统右下角的托盘串口。 3.点击托盘口的图标可以实现软件弹出窗口和最小化的切换。 1.参考办法 以下是判断C#窗体最小化到状态栏的状态的方法&#xff1a;…

[AI]文心一言爆火的同时,ChatGPT带来了这么多的开源项目你了解吗

前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家&#xff1a;https://www.captainbed.cn/z ChatGPT体验地址 文章目录 前言4.5key价格泄漏ChatGPT4.0使用地址ChatGPT正确打开方式最新功能语音助手存档…

Redis核心技术与实战【学习笔记】 - 7.Redis GEO类型 - 面向 LBS 应用的数据类型

前言 前面&#xff0c;介绍了 Redis 的 5 大基本数据类型&#xff1a;String、List、Hash、Set、Sorted Set&#xff0c;它们可以满足绝大多数的数据存储需求&#xff0c;但是在面对海里数据统计时&#xff0c;它们的内存开销很大。所以对于一些特殊的场景&#xff0c;它们是无…

计算机网络-物理层设备(中继器 集线器)

文章目录 中继器中继器的功能再生数字信号和再生模拟信号同一个协议 集线器&#xff08;多口中继器&#xff09;不具备定向传输的原因集线器是共享式设备的原因集线器的所有接口都处于同一个碰撞域&#xff08;冲突域&#xff09;内的原因 小结 中继器 中继器的功能 中继器的…

JVM 内存模型

1 什么是 JVM 内存模型 JVM 需要使用计算机的内存&#xff0c;Java 程序运行中所处理的对象或者算法都会使用 JVM 的内 存空间&#xff0c;JVM 将内存区划分为 5 块&#xff0c;这样的结构称之为 JVM 内存模型。 2 JVM 为什么进行内存区域划分 随着对象数量的增加&#xff…

基于二值化图像转GCode的单向扫描实现

基于二值化图像转GCode的单向扫描实现 什么是单向扫描单向扫描代码示例 基于二值化图像转GCode的单向扫描实现 什么是单向扫描 在激光雕刻中&#xff0c;单向扫描&#xff08;Unidirectional Scanning&#xff09;是一种雕刻技术&#xff0c;其中激光头只在一个方向上移动&a…

【Vue】二、Vue 组件展示控制的优雅解决方案

vue项目中展示的组件&#xff0c;我平常都是通过v-show进行展示控制&#xff0c;类似这样 通常情况下&#xff0c;一个正常展示组件的流程&#xff0c;是通过前端用户点击触发函数&#xff0c;在函数中对data数据进行操作&#xff0c;从而展示不同的页面 showWork: false, sho…

如何用Docker+jenkins 运行 python 自动化?

1.在 Linux 服务器安装 docker 2.创建 jenkins 容器 3.根据自动化项目依赖包构建 python 镜像(构建自动化 python 环境) 4.运行新的 python 容器&#xff0c;执行 jenkins 从仓库中拉下来的自动化项目 5.执行完成之后删除容器 前言 环境准备 Linux 服务器一台(我的是 CentOS7)…

GitHub工作流的使用笔记

文章目录 前言1. 怎么用2. 怎么写前端案例1&#xff1a;自动打包到新分支前端案例2&#xff1a;自动打包推送到gitee的build分支案例3&#xff1a;暂时略 前言 有些东西真的就是要不断的试错不断地试错才能摸索到一点点&#xff0c;就是摸索到凌晨两三点第二天要8点起床感觉要…