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

【算法】棋盘覆盖问题源代码及精简版

news 来源：原创 2025/5/13 21:50:14

一、题目

二、样例

三、示例代码

四、精简代码

五、总结

对于棋盘覆盖问题的解答和优化。

一、题目

输入格式：

第一行，一个整数n（棋盘n*n，n确保是2的幂次，n<64）

第二行，两个整数a和b, 特殊方格的位置，从左上开始计数a是列号（从1开始），b行号，从上到下，从1开始

输出格式：

n*n个整数

每行n个数，从左上开始，一行一行输出(最多8行），每个输出对应的L型块编号，输出数据占4位，不足前面补空格。

编号是递归从左上、右上、右下到左下的顺序进行。如下

二、样例

输入样例：

2 3

输出样例：

   3   3   4   4   8   8   9   9
   3   2   0   4   8   7   7   9
   5   2   2   6 10 10   7 11
   5   5   6   6   1 10 11 11
13 13 14   1   1 18 19 19
13 12 14 14 18 18 17 19
15 12 12 16 20 17 17 21
15 15 16 16 20 20 21 21

三、示例代码

#include<stdio.h>
#include <iostream>
using namespace std;#define MAX 1025
//问题表示
int k;                            //棋盘大小
int x,y;                        //特殊方格的位置
int board[MAX][MAX];
int tile=1;                                    //L型骨牌的编号,从1开始
void ChessBoard(int tr,int tc,int dr,int dc,int size) {if(size==1) return;                        //递归出口int t=tile++;                            //取一个L型骨，其牌号为tileint s=size/2;                            //分割棋盘//考虑左上角象限if(dr<tr+s && dc<tc+s)                    //特殊方格在此象限中ChessBoard(tr,tc,dr,dc,s);else {                                //此象限中无特殊方格board[tr+s-1][tc+s-1]=t;                //用t号L型骨牌覆盖右下角ChessBoard(tr,tc,tr+s-1,tc+s-1,s);    //将右下角作为特殊方格继续处理该象限}//考虑右上角象限if(dr<tr+s && dc>=tc+s)ChessBoard(tr,tc+s,dr,dc,s);        //特殊方格在此象限中else {                                //此象限中无特殊方格board[tr+s-1][tc+s]=t;                    //用t号L型骨牌覆盖左下角ChessBoard(tr,tc+s,tr+s-1,tc+s,s);      //将左下角作为特殊方格继续处理该象限}//处理左下角象限if(dr>=tr+s && dc<tc+s)                    //特殊方格在此象限中ChessBoard(tr+s,tc,dr,dc,s);else {                                //此象限中无特殊方格board[tr+s][tc+s-1]=t;                  //用t号L型骨牌覆盖右上角ChessBoard(tr+s,tc,tr+s,tc+s-1,s);    //将右上角作为特殊方格继续处理该象限}//处理右下角象限if(dr>=tr+s && dc>=tc+s)                    //特殊方格在此象限中ChessBoard(tr+s,tc+s,dr,dc,s);else {                                //此象限中无特殊方格board[tr+s][tc+s]=t;                      //用t号L型骨牌覆盖左上角ChessBoard(tr+s,tc+s,tr+s,tc+s,s);      //将左上角作为特殊方格继续处理该象限}
}int main() {int size;//size=8, x=3, y=6;cin>>size>>x>>y;x--, y--;ChessBoard(0, 0, x, y, size);for(int i=0; i<min(8, size); i++) {                //输出方案for(int j=0; j<size; j++)printf("%4d",board[i][j]);printf("\n");}
}

代码较为繁琐。可以利用设置offset来进行优化。

四、精简代码

在《Python Algorithms Mastering Basic Algorithms in the Python Language》里面有一段代码，就是对上面代码的精简。在国内各大网站都没有看见。本人也是觉得很唏嘘。

    def cover(board, lab=1, top=0, left=0, side=None):if side is None: side = len(board)# Side length s = side // 2# Offsets for outer/inner squares of subboardsoffsets = ((0, -1), (side-1, 0))for dy_outer, dy_inner in offsets:for dx_outer, dx_inner in offsets:# If the outer corner is not set...if not board[top+dy_outer][left+dx_outer]:# ... label the inner corner: board[top+s+dy_inner][left+s+dx_inner] = lab# Next label: lab += 1if s > 1:for dy in [0, s]:for dx in [0, s]:# Recursive calls, if s is at least 2:lab = cover(board, lab, top+dy, left+dx, s)# Return the next available label: return lab

可以运行下面代码验证，可知是正确的。

    board = [[0]*8 for i in range(8)]board[7][7] = -1cover(board)for row in board:print((" %2i"*8)%tuple(row))3  3  4  4  8  8  9  93  2  2  4  8  7  7  95  2  6  6 10 10  7 115  5  6  1  1 10 11 1113 13 14  1 18 18 19 1913 12 14 14 18 17 17 1915 12 12 16 20 17 21 2115 15 16 16 20 20 21 -1

五、总结

还得练。

【算法】棋盘覆盖问题源代码及精简版

目录一、题目二、样例三、示例代码四、精简代码五、总结对于棋盘覆盖问题的解答和优化。一、题目输入格式： 第一行，一个整数n（棋盘n*n，n确保是2的幂次，n<64） 第二行，两个整数…...

编程日记 2025/5/13 21:50:14

剖析kubernetes service的IP能否在宿主机中ping通

文章目录前言一、serviceIP是怎么产生的二、宿主机中ping serviceIP地址1.ping示例2.为什么ping不通剖析2.1.封装及解封装过程2.2.ICMP报文以太网数据帧格式2.3.原因三、ping不通svcIP是否跟iptables规则有关？四、为什么ipvs的的clusterIP类型的service能够ping通…...

编程日记 2025/5/12 9:16:56

路由VueRouter的基本使用

1.下载VueRouter到当前工程。 vue2：VueRouter3.x Vuex3.x。 vue3：VueRouter4.x Vuex4.x。在终端使用命令： year add vue-router3.6.5 2.引入。 import VueRouter from vue-router 3,安装注册。 Vue.use(VueRouter) 4…...

编程日记 2025/5/11 13:39:29

学习记录，正则表达式，隐式转换

正则表达式 \\：表示正则表达式 W: 表示一个非字（不是一个字，例如：空格，逗号，句号） W: 多个非字基本组成部分 1.字符字面量： 普通字符：在正则表达式中，大…...

编程日记 2025/5/13 21:30:25

Spring Boot + MySQL 多线程查询与联表查询性能对比分析

Spring Boot MySQL: 多线程查询与联表查询性能对比分析背景在现代 Web 应用开发中，数据库性能是影响系统响应时间和用户体验的关键因素之一。随着业务需求的不断增长，单表查询和联表查询的效率问题日益凸显。特别是在 Spring Boot 项目中&#xff0…...

编程日记 2025/5/12 13:37:42

C++小碗菜之二：软件单元测试

“没有测试的代码重构不能称之为重构，它仅仅是垃圾代码的到处移动” ——Corey Haines 目录前言什么是单元测试？ 单元测试的组成单元测试的命名单元测试的独立性 Google Test 单元测试的环境配置与使用 1. Ubuntu下安装 Google Test 2. 编写…...

编程日记 2025/5/11 18:05:19

集成学习综合教程

一、前置知识一个分类器的分类准确率在60%-80%，即：比随机预测略好，但准确率却不太高，我们可以称之为 “弱分类器”，比如CART（classification and regression tree 分类与回归树）。反之&#x…...

编程日记 2025/4/29 6:40:03

Java NIO channel

channel(通道)，byteBuffer(缓冲区)，selector（io多路复用），通道FileChannel,SocketChannel的transferTo,transferFrom,MappedByteBuffer实现了零拷贝。 JVM调操作系统方法，read,write，都可以送字…...

编程日记 2025/5/13 21:27:24

B3631 单向链表-模拟链表

来源 ：题目链接-洛谷 B3631 单向链表单向链表题目描述实现一个数据结构，维护一张表（最初只有一个元素 1 1 1）。需要支持下面的操作，其中 x x x 和 y y y 都是 1 1 1 到 1 0 6 10^6 106 范围内的正整数&…...

编程日记 2025/5/5 20:40:00

【C++】格式化输出详解：掌握 cout 的进阶用法

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 💯前言💯格式化输出的理论概述💯控制输出宽度和填充字符setw 操作符setfill 操作符 💯控制浮点数的显示格式fixed 与 scientificsetprecision 💯…...

编程日记 2025/5/10 4:25:59

【NoSQL数据库】Hbase基本操作——数据库表的增删改查

目录一、Hbase原理二、HBase数据库操作三、遇到的问题和解决方法一、Hbase原理 HBase的数据模型： 行键时间戳列族：contents 列族：anchor 列族：mime “com.cnn.www” T9 Achor:cnnsi.com”CNN” T8 Achor:…...

编程日记 2025/5/5 16:07:49

同步fifo

同步FIFO FIFO即是一种先进先出的数据缓存器。同步FIFO指的是数据的写入和读出的时钟是同一个时钟。异步 FIFO 有两个时钟信号，读和写逻辑用的各自的读写时钟。 FIFO没有外部读写地址线，使用起来简单。但是缺点就是只能先入先出，数据地址由…...

编程日记 2025/5/11 19:05:56

肌肉骨骼肿瘤治疗市场：潜力无限，未来可期

肌肉骨骼肿瘤治疗作为现代医学的重要分支，专注于应对骨骼和肌肉系统中的良性和恶性肿瘤。随着全球人口老龄化和生活方式的改变，肌肉骨骼疾病日益成为公共卫生的重要问题。与此同时，医疗技术的进步和患者对高质量医疗服务的需求不断推动该市场…...

编程日记 2025/5/5 23:55:20

高考倒计时：用倒计时软件为梦想加油可用于教室黑板或者电脑上

高考，这个被无数学子视为人生重要转折点的考试，即将来临。每一年的六月，都充满了紧张与期待。如何在这场人生的战役中取得胜利？除了日常的勤奋学习，科学的复习计划和心态调整外，一款好用的倒计时软件&#…...

编程日记 2025/5/10 21:00:11

人工智能学习用的电脑安装cuda、torch、conda等软件，版本的选择以及多版本切换

接触人工智能的学习三个月了，每天与各种安装包作斗争，缺少依赖包、版本高了、版本低了、不兼容了、系统做一半从头再来了。。。这些都是常态。三个月把单位几台电脑折腾了不下几十次安装，是时候总结一下踩过的坑和积累的经验了。以一个典型的…...

编程日记 2025/5/10 11:26:28

BERT模型的输出格式探究以及提取出BERT 模型的CLS表示，last_hidden_state[:, 0, :]用于提取每个句子的CLS向量表示

说在前面最近使用自己的数据集对bert-base-uncased进行了二次预训练，只使用了MLM任务，发现在加载训练好的模型进行输出CLS表示用于下游任务时，同一个句子的输出CLS表示都不一样，并且控制台输出以下警告信息。说是没有这些权重。…...

编程日记 2025/5/11 10:58:34

InfluxDB 集成 Grafana

将InfluxDB集成到Grafana进行详细配置通常包括以下几个步骤：安装与配置InfluxDB、安装与配置Grafana、在Grafana中添加InfluxDB数据源以及创建和配置仪表板。以下是一个详细的配置指南： 一、安装与配置InfluxDB 下载与安装： 从InfluxDB的官…...

编程日记 2025/5/10 3:12:04

Vue跨标签通讯(本地存储)(踩坑)

我司有一个需求【用户指引】需求是根标签有一个用户指引总开关，可以控制页面所有的用户指引是否在页面进入后初始是否默认打开，但是有些页面会新开标签这就设计到跨标签通讯了我采取的方案是本地存储重点:首先本地存储在页面是同源(即域名协议端口三…...

编程日记 2025/5/6 17:38:56

掌握创意之钥：全面解析HTML5 Canvas

在数字时代，表达创意的方式多种多样，而 HTML5 中的 <canvas> 元素无疑为网页开发者提供了一个强大的工具箱。无论你是想要创建动态图表、互动游戏还是复杂的可视化应用，掌握 Canvas 的基本用法都是迈向成功的关键一步。本文将带你一步步…...

编程日记 2025/5/11 2:43:24

mac port 安装redis 并设置为系统服务自定义配置方法

mac系统中，port 包管理工具比brew的速度快N倍，今天就给大家分享一下在macos系统中如何使用 port安装 redis数据库并配置为服务自动启动和自定义redis.conf配置的方法。 1. 安装redis sudo port install redis 2. 启动redis服务 sudo port load redis …...

编程日记 2025/5/10 10:23:37

Agent AI: Surveying the Horizons of Multimodal Interaction---摘要、引言、代理 AI 集成

题目智能体AI:多模态交互视野的考察论文地址：https://arxiv.org/abs/2401.03568 图1：可以在不同领域和应用程序中感知和行动的Agent AI系统概述。Agent AI是正在成为通用人工智能（AGI）的一个有前途的途径。Agent AI培训已经证…...

编程日记 2025/5/13 17:22:51

二百七十八、ClickHouse——将本月第一天所在的那一周视为第一周，无论它是从周几开始的，查询某个日期是本月第几周

一、目的 ClickHouse指标表中有个字段week_of_month，含义是这条数据属于本月第几周。而且将本月第一天所在的那一周视为第一周，无论它是从周几开始的。比如2024-12-01是周日，即12月第一周。而2024-12-02是周一，即12月第二周二…...

编程日记 2025/5/9 8:45:21

Unity 相机旋转及角度限制

前言由于欧拉角具有直观的可读性，做相机旋转时选择修改eulerAngles 来实现旋转，但实际效果与预期稍有不同，这是因为欧拉角受到万向锁（Gimbal Lock）的影响，在赋值时需要对输入的角度进行调整。 if (value…...

编程日记 2025/5/6 20:36:18

基于CentOS系统利用Kamailio搭建企业级SIP服务器

一、Kamailio简介 Kamailio是一款开源的SIP服务器，具有高性能、可扩展、模块化等特点。它广泛应用于VoIP、即时通讯、视频会议等领域。Kamailio支持多种操作系统，如Linux、FreeBSD等，可以与其他开源项目（如 Asterisk、FreeSWITCH…...

编程日记 2025/5/13 7:42:05

部署项目报错

vue2项目部署后 Error: Cannot find module /views/*** 1.起因登录页、首页等静态页面可以正常进入，后端访问也正常，可以获取到验证码。但是登录之后会发现首页空白或者进入不到首页 F12查看有报错信息：Error: Cannot find module ‘/v…...

编程日记 2025/5/5 8:09:37

【AIGC】大模型面试高频考点-位置编码篇

【AIGC】大模型面试高频考点-位置编码篇 （一）手撕绝对位置编码算法（二）手撕可学习位置编码算法（三）手撕相对位置编码算法（四）手撕 Rope 算法（旋转位置编码&#xf…...

编程日记 2025/5/7 12:14:17

钓鱼攻击详解：鱼叉攻击与水坑攻击

钓鱼攻击详解：鱼叉攻击与水坑攻击在现代网络安全领域中，钓鱼攻击（Phishing）是一种最常见且有效的攻击手段。它通过欺骗用户，引导其泄露敏感信息或执行恶意操作，从而为攻击者打开大门。本文将深入介绍两种…...

编程日记 2025/5/9 2:17:13

如何在自动化安全测试中，实现多工具集成与数据融合，以提高对Spring Boot应用程序安全漏洞的检测效率与准确性？

为了在自动化安全测试中实现多工具集成与数据融合，以提高对Spring Boot应用程序安全漏洞的检测效率与准确性，可以采取以下策略和方法： 文章目录 1. 工具选择与集成2. 数据标准化与聚合3. 数据分析与融合4. 持续改进5. 实施示例 1. 工具选择与…...

编程日记 2025/5/7 5:55:59

框架篇面试

一、Spring框架中的单例bean的安全性 Spring框架中有一个Scope注解，默认的值就是singleton，单例的；因为一般在spring的bean中注入的都是无状态的对象，所以没有线程安全问题。但是如果在bean中定义了可修改的成员变量，…...

编程日记 2025/5/13 2:10:11

STM32滴答定时器SysTick理解+时基设置(4.1)

文章目录 1. 什么是滴答定时器？2. SysTick定时器初始化2.1 systick定时器时钟源？2.2 定时器四个寄存器 3 函数设置3.1SysTick_Config（uint32_t ticks）函数3.2初始化函数 4. 延时函数实现4.1 ms延时思路及实现4.2 us延时 1. 什么是…...

编程日记 2025/5/12 14:42:50

数字化时代下的企业合规管理：全球化背景下的挑战与机遇

在全球化浪潮的推动下，企业合规管理已成为企业发展中不可或缺的一部分。随着各国法规日益严格，以及数字化技术的飞速发展，企业在扩展业务的同时，也面临着越来越多的合规挑战。有效的合规管理不仅有助于提高企业的管理水平和运营效…...

编程日记 2025/5/9 10:50:06

读《Effective Java》笔记 - 条目17

条目17：使可变性最小化为什么要使可变性最小化？ 不可变对象天然是线程安全的，可以在多个线程之间安全共享。而可变对象需要添加额外的同步机制保证线程安全。不可变对象一旦创建就不会改变，便于追踪和理解代码。而可变对象的状态…...

编程日记 2025/5/11 14:25:22

对比json数据是否变化

在 JavaScript 中，你可以使用多种方法来对比两个 JSON 数据是否发生变化。以下是几种常见的方式： 1. 使用 JSON.stringify 最简单的方法是将两个 JSON 对象序列化为字符串，并比较这些字符串。但需要注意的是，这种方法对于对象属…...

编程日记 2025/5/2 9:57:54

云计算实验室建设方案

一、云计算实验室建设方案云计算实验教学整体解决方案，包括：云计算服务器集群、云计算实训平台、实训课程体系、行业实战课程系统、行业数据等，系统性地解决云计算实训教学的痛点问题。【硬件系统】云计算实训一体机云计算实训一体机是唯…...

编程日记 2025/5/12 8:04:42

一、理论基础-PSI

之前参加了隐语第2期，对隐语SecretFlow框架有了大致的了解，这次参加隐语第4期，学习下PSI和PIR。一、PSI定义首先介绍PSI的定义，PSI（隐私集合求交，Private Set Intersection即PSI)是安全多方计算&#x…...

编程日记 2025/5/12 14:09:31

C++学习0.2: RAII

引用： 【代码质量】RAII在C编程中的必要性_raii 在c中的重要性-CSDN博客 C RAII典型应用之lock_guard和unique_lock模板_raii lock-CSDN博客前言: 常用的线程间同步/通信（IPC）方式有锁（互斥锁、读写锁、自旋锁）、…...

编程日记 2025/5/10 5:10:31

机器学习基础

了解机器学习的基本概念，如监督学习、无监督学习、强化学习、模型评估指标（准确率、召回率、F1分数等）。机器学习（Machine Learning，ML）是人工智能（AI）的一个分支，它使计…...

编程日记 2025/5/9 22:30:03

传输层TCP_三次握手四次挥手的过程

三次握手四次挥手三次握手三次握手...

编程日记 2025/4/24 18:27:22

AI主流的生成式工作流框架

根据搜索结果，以下是一些2024年比较主流的生成式工作流框架： 1. LangChain：LangChain是一个用于构建生成式AI工作流的开发框架，它支持多种语言模型、工具、数据源及其他系统的集成。 2. DSPy：DSPy是一个生成式AI工作…...

编程日记 2025/5/8 5:46:28

【WRF后处理】WRF时区（UTC）需转化为北京时间（CST）！！！

目录 WRF运行时间标准注意事项-本地时区问题输入数据：ERA5时间标准ERA5数据和WRF模型需要转换为北京时间！！！北京时间（CST）与协调世界时（UTC）的关系转换方法参考 WRF运行时间标准 …...

编程日记 2025/5/13 5:23:48

Qt 2D绘图之五：图形视图框架的结构、坐标系统和框架间的事件处理与传播

参考文章链接： Qt 2D绘图之五：图形视图框架的结构和坐标系统 Qt 2D绘图之六：图形视图框架的事件处理与传播图形视图框架的结构在前面讲的基本绘图中，我们可以自己绘制各种图形，并且控制它们。但是，如果需要同时绘制很多个相同或不同的图形，并且要控制它们的移动、…...

编程日记 2025/5/10 8:31:42

游戏引擎学习第34天

仓库:https://gitee.com/mrxiao_com/2d_game #这天内容比较多开场介绍游戏开发行业的基础是使用C和C编程，这是当今几乎所有游戏的开发标准。市面上广受欢迎的游戏，如《使命召唤》或《侠盗猎车手》，它们的底层代码和引擎几乎无一例外地采…...

编程日记 2025/5/13 0:27:41

深度学习笔记——模型压缩和优化技术（蒸馏、剪枝、量化）

本文详细介绍模型训练完成后的压缩和优化技术：蒸馏、剪枝、量化。文章目录 1. 知识蒸馏 (Knowledge Distillation)基本概念工作流程关键技术类型应用场景优势与挑战优势挑战总结 2. 权重剪枝 (Model Pruning)基本原理二分类1. 非结构化剪枝（Unstructur…...

编程日记 2025/5/12 17:39:40

[在线实验]-RabbitMQ镜像的下载与部署

镜像下载 docker的rabbitmq镜像资源-CSDN文库加载镜像 docker load --input rabbitmq.tar 给镜像打标签这里发现镜像名为none，需要给镜像重命名下 docker tag [镜像id] [新镜像名称]:[新镜像标签] docker tag ebaf409ffbe2 rabbitmq:management 运行镜像…...

编程日记 2025/5/9 5:21:18

Netty 入门应用：结合 Redis 实现服务器通信

在上篇博客中，我们了解了 Netty 的基本概念和架构。本篇文章将带你深入实践，构建一个简单的 Netty 服务端，并结合 Redis 实现一个数据存取的示例。在这个场景中，Redis 作为缓存存储，Netty 作为服务端处理客户端请求。通…...

编程日记 2025/5/5 17:48:32

【新品发布】ESP32-P4开发板 —— 启明智显匠心之作，为物联网及HMI产品注入强劲动力

核心亮点： ESP32-P4开发板，是启明智显精心打造的一款高性能物联网开发板。它专为物联网项目及HMI（人机界面）产品而设计，旨在为您提供卓越的性能和稳定可靠的运行体验。强大硬件配置： 双核400MHz RISC-V处…...

编程日记 2025/5/10 0:50:06

MeterSphere 使用脚本处理数据

1、前置/后置脚本支持BeanShell(JSR223)、python、groovy、JavaScript脚本语言，推荐BeanShell(JSR223)。在前置脚本中可以直接引用JMeter 预定义对象，例如： -- log：用于在脚本执行过程中打印日志 //打印“Hello World!”到info…...

编程日记 2025/5/7 0:46:38

如何获取谷歌新闻API密钥？

在信息获取和新闻传播领域，快速获取最新的新闻动态至关重要。谷歌新闻API为开发者提供了强大的工具，能够方便地集成全球各类新闻内容。通过使用该API，开发者可以实现对新闻的实时访问和管理，为用户提供丰富的信息服务。本文将指导…...

编程日记 2025/5/9 17:52:15

【全网最新】若依管理系统基于SpringBoot的前后端分离版本开发环境配置

目录提前准备： 下载源代码设置依赖设置后台连接信息运行后台运行前端安装npm依赖启动前端登录网页客户端提前准备： 1、安装mysql 5以上就可以。 2、安装redis. 3、安装npm npm下载地址：https://nodejs.org/dist/v22.12…...

编程日记 2025/5/9 6:45:37

一、题目

二、样例

三、示例代码

四、精简代码

五、总结

相关文章：