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

棋盘问题（DFS）

news 来源：原创 2025/8/23 17:57:48

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。

要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 kk 个棋子的所有可行的摆放方案数目 CC。

输入格式

输入含有多组测试数据。

每组数据的第一行是两个正整数 n,kn,k，用一个空格隔开，表示了将在一个 n∗nn∗n 的矩阵内描述棋盘，以及摆放棋子的数目。当为-1 -1时表示输入结束。

随后的 nn 行描述了棋盘的形状：每行有 nn 个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出格式

对于每一组数据，给出一行输出，输出摆放的方案数目 CC （数据保证 C<231C<231）。

数据范围

n≤8,k≤nn≤8,k≤n

输入样例：
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
输出样例：
2
1

题目链接：1114. 棋盘问题 - AcWing题库

学习链接：DFS正确入门方式 | DFS + 递归与递推习题课(下) | 一节课教你爆搜!_哔哩哔哩_bilibili

解题思路：
  1.  确保每行只放一枚棋子，每一行都有 n 列个选择，但要保证棋子是放在'#'棋盘区域，且该列未被标记过
  2. 设置有个标记数组st[]，标记某列一存在棋子，则后续行就不可以放棋子在该列
  3. 当枚举够k个棋子（位置）时，结束搜索
  4. 找到方案后，需要回溯
  5. 当某行不放置棋子时，可直接进入下一行进行枚举
  6. 累计方案数

代码如下： 

#include<bits/stdc++.h>
using namespace std;
int n;//矩阵大小
int k;//k个棋子
char ch[10][10];//棋盘矩阵 
int st[10];//标记某列已存在棋子
int cnt;//累计方案数void dfs(int x,int sum)
{//如果已枚举够了k个棋子，累计方案数if(sum==k){cnt++;return ;} //如果枚举的位置(从0开始)越界if(x>=n)	return ;for(int j=0;j<n;j++){//如果该位置(x,j)是棋盘区域，且该列未被标记过if(ch[x][j]=='#' && st[j]==0){//标记该列st[j]=1;//枚举下一个位置 dfs(x+1,sum+1);//恢复现场st[j]=0; } }//若该行不放棋子，直接进入到下一行开始搜索dfs(x+1,sum); 
} 
int main()
{while(cin>>n>>k && n!=-1 &&k!=-1){cnt=0;for(int i=0;i<n;i++){cin>>ch[i];//输入一行字符 } //从第一行第一列开始枚举,当前已放置的棋子总数sum=0 dfs(0,0);cout<<cnt<<endl; }return 0;
}

 希望能帮助到各位同志，祝天天开心，学业进步！

相关文章：

棋盘问题（DFS）

在一个给定形状的棋盘&#xff08;形状可能是不规则的&#xff09;上面摆放棋子&#xff0c;棋子没有区别。 要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列&#xff0c;请编程求解对于给定形状和大小的棋盘&#xff0c;摆放 kk 个棋子的所有可行的摆放方案数目 C…...

编程日记 2025/8/23 17:57:48

verilog学习--1、语言要素

先看一个例子 /*This is first Verilog progaram*/ timescale 1ns/1ns module HalfAdder(A,B,Sum,Carry);input A,B;output Sum, Carry; /**/assign #2 SumA^B;assign #5 CarryA&B&#xff1b; endmodule; Verilog以module为单位编写&#xff0c;每个文件一个module&#…...

编程日记 2025/8/21 17:54:29

from fastmcp import FastMCP和from mcp.server.fastmcp import FastMCP的区别是什么？

文章目录 困惑以方式一开启一个mcp server，并用cline进行调用mcp install server.py修改配置文件以方式二开启MCP server困惑 一直比较困惑的是，好像用python实现mcp server有两种实现方式。 一是使用： https://github.com/modelcontextprotocol/python-sdk 二是使用： …...

编程日记 2025/8/24 3:54:29

QT工程建立

打开软件新建一个工程 选择chose 工程命名&#xff0c;选择保存路径&#xff0c;可以自己选择&#xff0c;但是不要有中文路径 默认的直接下一步 任意选一个下一步 点击完成 之后是这个界面&#xff0c;点击右下角的绿色三角形编译一下 实验内容 添加类 第一个是建立cpp和.h文件…...

编程日记 2025/8/22 5:24:35

Day82 | 灵神 | 快慢指针 重排链表

Day82 | 灵神 | 快慢指针 重排链表 143.重排链表 143. 重排链表 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者直接给跪了&#xff0c;这个难度真是mid吗 直接去看灵神的视频 环形链表II【基础算法精讲 07】_哔哩哔哩_bilibili 1.简单来说就是&#xf…...

编程日记 2025/8/24 3:54:29

TCN-LSTM时间卷积长短期记忆神经网络多变量时间序列预测（Matlab完整源码和数据）

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.TCN-LSTM时间卷积长短期记忆神经网络多变量时间序列预测&#xff08;Matlab完整源码和数据&#xff09; 2.运行环境为Matlab2023b&#xff1b; 3.data为数据集&#xff0c;输入多个特征&#xff0c;输出单个变量&a…...

编程日记 2025/8/24 3:52:10

语法: lcd_load( buffer_pointer, offset, length)；

LCD_LOAD() 语法: lcd_load( buffer_pointer, offset, length); 参数: buffer_pointer指向发送给LCD的用户数据; offset是用来将该数据写入LCD,用作进入LCD segment memory的偏移量; length是传送的字节数. 要求: 没有. 功能: 该函数将从CPU的buffer_pointer存储区…...

编程日记 2025/8/24 3:53:32

分治（8题）

目录 一、快排 1.颜色分类 2.排序数组 3.数组中的第k个最大元素 4.最小的K个数 二、归并 1. 排序数组 2.数组中的逆序对 3.计算右侧小于当前元素的个数 4.翻转对 一、快排 1.颜色分类 75. 颜色分类 - 力扣&#xff08;LeetCode&#xff09; left和right&#xff0c;初…...

编程日记 2025/8/24 3:52:15

【9】数据结构的串篇章

目录标题 串的定义顺序串的实现初始化赋值打印串求串的长度复制串判断两个串长度是否相等连接两个串比较两个串内容是否相等插入操作删除操作调试与代码合集 串的模式匹配算法朴素的模式匹配算法KMP算法实现模式匹配 串的定义 定义&#xff1a;由0个或多个字符组成的有限序列&…...

编程日记 2025/8/19 21:52:07

Linux file命令

目录 一. file命令简介二. -b 输出结果不显示文件名三. --mime 输出文件的MIME类型字符串四. 批量确认文件类型4.1 -f 从指定的文件中读取文件路径&#xff0c;显示其文件类型4.2 配合find命令查找确认 一. file命令简介 由于Linux系统并不是像Windows系统那样通过扩展名来定义…...

编程日记 2025/8/24 3:54:30

ARM-UART

时钟选择PLCK,超时3ms自动发送&#xff0c;设置发送8位的缓冲区&#xff0c;且发送中断 设置触发深度&#xff0c;达到8字节将缓冲区数据发憷 中断处理函数...

编程日记 2025/8/24 3:52:12

AFT3 Engine传奇世界AFT3代引擎源码

此AFT3代引擎源码&#xff0c;不是老AFT0330版本&#xff0c;应该是WeiAFT的源码 本源码为新AFT3引擎源码&#xff0c;直接电脑打包出来&#xff0c; 现在市面上使用的AFT3引擎都是用的此款&#xff0c;下载编译即用 链接: https://pan.baidu.com/s/1Zxa64AQ7MUsdV2iIrqiTEg 提…...

编程日记 2025/8/24 3:52:13

[ 3分钟算法 ] | 递归搜索题目 : 翻转链表(递归版)

目录 1. 题目链接&#xff1a; 2. 思路分析&#xff1a; 思路一&#xff1a;从宏观上看 思路二&#xff1a;将链表看成一颗树 3. 代码 1. 题目链接&#xff1a; LCR 024. 反转链表 2. 思路分析&#xff1a; 思路一&#xff1a;从宏观上看 让当前节点后面的链表先逆置&…...

编程日记 2025/8/24 3:54:30

左值与右值，空间与数据

左值是空间&#xff0c;右值是数据 编程总是对“数据”&#xff0c;对"存放数据的空间"操作 a返回一个当前的数据&#xff0c;存放到一个临时空间中&#xff0c;自身的空间中的数据再进行运算 a直接对自身空间中的数据进行运算 其余知识&#xff1a; 1.变量名的意…...

编程日记 2025/8/24 3:54:29

线程池/内存池/mysql连接池

线程池介绍 ①线程池定义&#xff1a; 维持和管理固定数量线程的结构&#xff0c;用于解决资源频繁创建和销毁的问题。 ②线程池组成&#xff1a; 固定数量的线程、队列、任务状态管理。 ④线程池的作用&#xff1a; 避免频繁创建和销毁线程&#xff0c;管理线程状态&…...

编程日记 2025/8/24 3:53:31

图解AUTOSAR_SWS_FlexRayARTransportLayer

FlexRay AUTOSAR 传输层 (FrArTp) 分析 1. AUTOSAR FlexRay 传输层架构 1.1 FlexRay AUTOSAR 传输层在AUTOSAR架构中的位置 AUTOSAR分层架构中，FlexRay AUTOSAR 传输层(FrArTp)位于通信抽象层，其上方是PDU路由器，下方是FlexRay接口。FrArTp的主要功能是实现FlexRay网络上的…...

编程日记 2025/8/24 3:53:32

【百日精通JAVA | SQL篇 | 第四篇】约束

SQL这一块没什么难度&#xff0c;主要是一个熟练度&#xff0c;稍微上点难度的地方&#xff0c;其实在于查&#xff0c;比较复杂&#xff0c;涉及到很多问题。 指定列插入 使用指定列插入的时候&#xff0c;未被指定的列使用默认值进行存储&#xff0c;默认值为空。 默认值设置…...

编程日记 2025/8/20 1:37:08

QEMU源码全解析 —— 块设备虚拟化（16）

接前一篇文章：QEMU源码全解析 —— 块设备虚拟化（15） 本文内容参考： 《趣谈Linux操作系统》 —— 刘超，极客时间 《QEMU/KVM源码解析与应用》 —— 李强，机械工业出版社 《KVM实战 —— 原理、进阶与性能调优》—— 任永杰 程舟，机械工业出版社...

编程日记 2025/8/24 3:55:43

实验：IS-IS认证。

一、IS-IS认证的定义与作用分析 ‌IS-IS认证是什么&#xff1f;‌ IS-IS&#xff08;Intermediate System to Intermediate System&#xff09;协议是用于自治系统内部的路由协议&#xff0c;其认证机制主要用于保障路由信息交换的安全性&#xff0c;包括‌邻居关系建立‌和‌…...

编程日记 2025/8/24 3:52:15

11-产品经理-创建产品

在“产品”-“仪表盘”内&#xff0c;可以查看系统中关于产品及相关需求的统计。 在“产品”-“产品列表”页面&#xff0c;可以按项目集、项目查看其关联产品。还可以添加产品、编辑产品线、或者导出产品列表。 产品看板&#xff0c;通过看板方式查看产品、产品计划和产品下的…...

编程日记 2025/8/22 18:59:31

玄机-应急响应-入侵排查

靶机排查目标&#xff1a; 1.web目录存在木马&#xff0c;请找到木马的密码提交 查看/var/www/html。 使用find命令查找 find ./ -type f -name "*.php | xargs grep "eval("查看到1.php里面存在无条件一句话木马。 2.服务器疑似存在不死马&#xff0c;请找…...

编程日记 2025/8/22 14:48:02

MySQL基础知识（通俗版）

MySQL基础知识&#xff08;通俗版&#xff09; 一、MySQL基础概念 1.1 MySQL简介 想象MySQL就像一个超级大的Excel表格&#xff0c;但它比Excel更强大&#xff1a; 可以同时处理成千上万的数据可以保证数据的安全性和一致性可以支持多人同时操作可以自动备份和恢复数据 1.…...

编程日记 2025/8/20 12:27:22

python逆向：喜马拉雅登录案例

网址&#xff1a;登录 1. 点击到网页主页 先随便输入电话号码和密码 打开开发者工具&#xff0c;点击网络清空&#xff0c;然后点击登录发起网络请求 &#xff08;出现一个请求包&#xff0c;我们发现不是我们所需要的&#xff09; 我们进行验证滑块&#xff0c;就又出来请求…...

编程日记 2025/8/20 2:27:13

windows AndroidStudio上传maven中央仓库

一、插件地址&#xff1a;https://github.com/vanniktech/gradle-maven-publish-plugin?tabreadme-ov-file 二、Maven中心&#xff1a;https://vanniktech.github.io/gradle-maven-publish-plugin/central/ 2.1、中央门户帐户&#xff0c;用github账号登陆&#xff1a;gh122…...

编程日记 2025/8/19 23:19:14

嵌入式学习(35)-STM32F103 TXE 和TC

在USART的发送端有2个寄存器&#xff0c;一个是程序可以看到的USART_DR寄存器,另一个是程序看不到的移位寄存器,对应USART数据发送有两个标志&#xff0c;一个是TXE发送数据寄存器空&#xff0c;另一个是TC发送结束。 当USART_DR中的数据传送到移位寄存器后&#xff0c;TXE被设…...

编程日记 2025/8/22 1:07:13

linux Gitkraken 破解

ubuntu 安装 Gitkraken 9.x Pro 版本_gitcracken.git-CSDN博客...

编程日记 2025/8/17 22:22:44

Qwen-Agent框架的文件相关操作：从Assistant到BasicDocQA

在前面的几篇文章如《针对Qwen-Agent框架的Function Call及ReAct的源码阅读与解析&#xff1a;Agent基类篇》 、《基于Qwen-Agent框架的Function Call及ReAct方式调用自定义工具》、 《针对Qwen-Agent框架的源码阅读与解析&#xff1a;FnCallAgent与ReActChat篇》中&#xff0c…...

编程日记 2025/8/23 8:11:03

2025年3月15日（5mw）

根据《NREL/TP-500-38060技术报告》&#xff0c;NREL 5-MW参考风力机的各部件质量及总体质量数据如下&#xff1a; 各部件质量数据 叶片&#xff08;Blades&#xff09; 单叶片质量&#xff1a;17,740 kg&#xff08;见表2-2&#xff09;总数&#xff1a;3片总质量&#xff1a;…...

编程日记 2025/8/21 21:39:54

docker mysql 笔记250406

docker mysql 笔记250406 以下是使用 Docker 运行 MySQL 的完整指南&#xff0c;包含常见配置和最佳实践&#xff1a; 1. 快速启动 MySQL 容器 docker run -d \--name mysql_db \-e MYSQL_ROOT_PASSWORDmy-secret-pw \-p 3306:3306 \mysql:8.02. 关键配置说明 2.1 环境变量&…...

编程日记 2025/8/21 5:11:49

ceph集群架构阐述

ceph集群架构阐述 ​ 首先&#xff0c;ceph集群也是分为客户端和服务端的&#xff0c;是一种高效的分布式存储系统&#xff0c;我们将其拆分为这两个部分来进行分析。 ​ 我大致的将服务端分为API类型、逻辑层、OSD层三个层面进行分析&#xff1b;将客户端按三种API类型挂载、…...

编程日记 2025/8/17 23:35:00

《Java八股文の文艺复兴》第十篇：量子永生架构——对象池的混沌边缘

目录 卷首语&#xff1a;蝴蝶振翅引发的量子海啸 第一章&#xff1a;混沌初开——对象池的量子涅槃&#xff08;深度扩展&#xff09; 第二章&#xff1a;混沌计算——对象复活的降维打击&#xff08;技术深化&#xff09; 第三章&#xff1a;量子试炼场——亿万级对象池全…...

编程日记 2025/8/19 11:51:25

(linux操作系统)程序地址空间

程序地址空间是什么&#xff1f; 讲这个问题之前&#xff0c;我们先来看一段熟悉的代码&#xff0c;以前学习C语言或者C语言时&#xff0c;就听说过程序内存分布&#xff0c;堆区&#xff0c;栈区&#xff0c;静态区&#xff0c;常量区&#xff0c;共享区&#xff0c;代码段&am…...

编程日记 2025/8/20 15:56:05

专业抑郁测试工具：让心理健康评估更简单

专业抑郁测试工具&#xff1a;让心理健康评估更简单 在这个快节奏的社会中&#xff0c;心理健康问题越来越受到人们的关注。为了帮助大家更好地了解自己的心理状态&#xff0c;我们开发了一款专业的在线抑郁测试工具。这个工具基于科学的心理量表设计&#xff0c;为用户提供准…...

编程日记 2025/8/21 10:49:57

C语言中单向链表：创建节点与插入新节点

一. 简介 单链表是一种常见且基础的数据结构&#xff0c;由一系列节点组成&#xff0c;每个节点包含数据和一个指向下一个节点的指针。 本文简单学习一下C语言中如何实现单项链表。 二. C语言实现单向链表 单向链表&#xff1a;单向链表是一种线性数据结构&#xff0c;由一…...

编程日记 2025/8/22 10:35:26

jsoncpp的使用

json提供的几个类&#xff1a; Value类&#xff1a;将json支持的数据类型进行包装&#xff0c;最终得到一个Value类型 FastWriter类&#xff1a;将Value对象中的数据序列化为字符串&#xff0c;序列化后可以得到json格式的字符串 Reader类&#xff1a;反序列化&#xff0c;将…...

编程日记 2025/8/22 2:28:22

【最新版】啦啦外卖v64系统独立版源码+全部小程序APP端+安装教程

一.系统介绍 啦啦外卖跑腿平台独立版&#xff0c;使用的都知道该系统功能非常强大&#xff0c;应该说是目前外卖平台功能最全的一套系统。主要是功能非常多&#xff0c;拿来即用&#xff0c;包括客户端小程序、配送端小程序、商户端小程序&#xff0c;还有对应四个端的APP源码…...

编程日记 2025/8/19 4:49:56

13-产品经理-产品多分支平台管理

禅道16.0版本开始&#xff0c;优化和增强了产品的分支/平台功能&#xff0c;主要特点如下&#xff1a; 多分支/平台功能兼容各种大小型项目&#xff0c;项目/迭代可以关联对应产品的某个分支/平台。分支/平台支持灵活管理&#xff0c;可以把分支/平台理解为时间层面的概念&…...

编程日记 2025/8/19 2:55:05

AI在医疗领域的应用

人工智能对医疗领域的革命性影响 一、智能诊断系统的突破 病理识别准确率提升乳腺癌检测准确率达94.6%（2023《Nature Medicine》）皮肤癌诊断灵敏度超过专业医师12%多模态诊断整合融合CT/MRI影像+基因组数据+电子病历急性肾损伤预测提前48小时（DeepMind）二、药物研发范式革…...

编程日记 2025/8/22 10:15:19

LabVIEW 在故障诊断中的算法

在故障诊断领域&#xff0c;LabVIEW 凭借其强大的图形化编程能力、丰富多样的工具包以及卓越的功能性能&#xff0c;成为工程师们进行故障诊断系统开发的得力助手。通过运用各种算法&#xff0c;能够对采集到的信号进行全面、深入的分析处理&#xff0c;从而准确地诊断出系统中…...

编程日记 2025/8/20 14:40:18

（自用）WebSocket创建流程

在Spring Boot项目中新建WebSocket服务&#xff0c;可以按照以下详细步骤进行操作&#xff1a; 1.创建Spring Boot项目 可以通过Spring Initializr&#xff08;<>&#xff09;快速创建一个新的Spring Boot项目&#xff0c;添加Spring Web和Spring Boot DevTools依赖&…...

编程日记 2025/8/22 9:48:23

C++多线程编码二

1.lock和try_lock lock是一个函数模板&#xff0c;可以支持多个锁对象同时锁定同一个&#xff0c;如果其中一个锁对象没有锁住&#xff0c;lock函数会把已经锁定的对象解锁并进入阻塞&#xff0c;直到多个锁锁定一个对象。 try_lock也是一个函数模板&#xff0c;尝试对多个锁…...

编程日记 2025/8/19 8:45:10

【最新版】金媒婚恋系统v10.5最新稳定开源+原生前端小程序 PC端+安装教程

一.系统简介 1. 红娘服务 红娘服务模块是该系统的一大特色。专业红娘会通过分析用户的个人资料和偏好&#xff0c; 为用户提供精准的配对建议和个性化服务。用户可以预约红娘服务&#xff0c;通过红娘的介入&#xff0c;提升配对成功率。 2. 相亲活动 相亲活动模块用于组织和管…...

编程日记 2025/8/20 8:55:20

[spring] spring AOP - 面向切面编程の学习

[spring] spring AOP - 面向切面编程の学习 几年前开始还在被 spring 的八股文时&#xff0c;AOP 就是一个比较热也比较大的点&#xff0c;为了面试确实背过不少&#xff0c;不过 AOP 实现本身做的不多&#xff0c;一方面也是因为 AOP 一旦配置好了基本上就不需要改什么&#…...

编程日记 2025/8/23 8:12:11

JavaScript 中的 Reflect 详解

Reflect 是 ES6引入的一个内置对象&#xff0c;它提供了一系列静态方法来操作对象&#xff0c;这些方法与 Proxy 处理器方法一一对应。Reflect 的设计目的是为了更优雅地操作对象&#xff0c;并统一某些操作的行为。 1. Reflect 的基本特点 1. 不是构造函数&#xff1a;不能使…...

编程日记 2025/8/21 14:00:31

【操作系统】linux常用命令

UP作为一个Linux系统练习两年半的个人练习生&#xff0c;今天分门别类地给大家整理一下常用的Linux命令&#xff0c;祝大家在Linux练习之路一帆风顺。 文件和目录操作 文件查看与编辑 文件查找 文件权限与所有权 进程管理 系统信息与监控 网络管理与诊断...

编程日记 2025/8/18 1:00:36

002 vue组件化编程

文章目录 一般方式全局组件局部组件 组件&#xff08;Component&#xff09;是Vue.js最强大的功能之一 组件也是一个Vue实例&#xff0c;也包括&#xff1a;data、methods、生命周期函数等 组件渲染需要html模板&#xff0c;所以增加了template属性&#xff0c;值就是HTML模板 …...

编程日记 2025/8/21 18:50:32

常见的 JavaScript 框架和库

在现代前端开发中&#xff0c;JavaScript框架和库成为了构建高效、可维护应用程序的关键工具。本文将介绍四个常见的JavaScript框架和库&#xff1a;React、Vue.js、Angular 和 Node.js&#xff0c;并探讨它们的特点、使用场景及适用场合。 1. React — 构建用户界面的JavaScri…...

编程日记 2025/8/21 7:54:41

005_循环结构

循环结构 循环结构的作用和应用场景for循环while循环for和while的使用规范do - while 死循环循环嵌套break、continueRandom生成随机数 循环结构的作用和应用场景 减少代码的重复编写、灵活的控制程序的执行 for循环 for (1初始化语句; 2循环条件; 3迭代语句){4循环体语句(重…...

编程日记 2025/8/18 0:17:48

1110+款专业网站应用程序UI界面设计矢量图标figma格式素材 Icon System | 1,100+ Icons Easily Customize

1110款专业网站应用程序UI界面设计矢量图标figma格式素材 Icon System | 1,100 Icons Easily Customize 产品特点 — 24 x 24 px 网格大小 — 2px 线条描边 — 所有形状都是基于矢量的 — 平滑和圆角 — 易于更改颜色 类别 &#x1f6a8; 警报和反馈 ⬆️ 箭头 &…...

编程日记 2025/8/19 7:40:13

leetcode 368. 最大整除子集 中等

给你一个由 无重复 正整数组成的集合 nums &#xff0c;请你找出并返回其中最大的整除子集 answer &#xff0c;子集中每一元素对 (answer[i], answer[j]) 都应当满足&#xff1a; answer[i] % answer[j] 0 &#xff0c;或answer[j] % answer[i] 0 如果存在多个有效解子集&…...

编程日记 2025/8/23 11:24:53