【算法】棋盘覆盖问题源代码及精简版
目录
一、题目
二、样例
三、示例代码
四、精简代码
五、总结
对于棋盘覆盖问题的解答和优化。
一、题目

输入格式:
第一行,一个整数n(棋盘n*n,n确保是2的幂次,n<64)
第二行,两个整数a和b, 特殊方格的位置,从左上开始计数a是列号(从1开始),b行号,从上到下,从1开始
输出格式:
n*n个整数
每行n个数,从左上开始,一行一行输出(最多8行),每个输出对应的L型块编号,输出数据占4位,不足前面补空格。
编号是递归从左上、右上、右下到左下的顺序进行。如下

二、样例
输入样例:
8
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) 第二行,两个整数…...
Django的介绍
Django是一个高级的Python Web框架,它鼓励快速开发和干净、实用的设计。Django遵循MVC设计模式,即模型(Model)、视图(View)和控制器(Controller),并提供了一个即时可用的…...
【Spring工具插件】lombok使用和EditStarter插件
阿华代码,不是逆风,就是我疯 你们的点赞收藏是我前进最大的动力!! 希望本文内容能够帮助到你!! 目录 引入 一:lombok介绍 1:引入依赖 2:使用 3:原理 4&…...
掌控时间,成就更好的自己
在个人成长的道路上,时间管理是至关重要的一环。有效的时间管理能够让我们更加高效地完成任务,实现自己的目标,不断提升自我。 时间对每个人都是公平的,一天只有 24 小时。然而,为什么有些人能够在有限的时间里做出卓…...
Ruby On Rails 笔记2——表的基本知识
Active Record Basics — Ruby on Rails Guides Active Record Migrations — Ruby on Rails Guides 原文链接自取 1.Active Record是什么? Active Record是MVC模式中M的一部分,是负责展示数据和业务逻辑的一层,可以帮助你创建和使用Ruby…...
【AI系统】EfficientNet 系列
EfficientNet 系列 本文主要介绍 EffiicientNet 系列,在之前的文章中,一般都是单独增加图像分辨率或增加网络深度或单独增加网络的宽度,来提高网络的准确率。而在 EfficientNet 系列论文中,会介绍使用网络搜索技术(NAS)去同时探索…...
【Python小白|Python内置函数学习2】Python有哪些内置函数?不需要导入任何模块就可以直接使用的!现在用Python写代码的人还多吗?
【Python小白|Python内置函数学习2】Python有哪些内置函数?不需要导入任何模块就可以直接使用的!现在用Python写代码的人还多吗? 【Python小白|Python内置函数学习2】Python有哪些内置函数?不需要导入任何模块就可以直接使用的&a…...
蓝桥杯分治
P1226 【模板】快速幂 题目描述 给你三个整数 𝑎,𝑏,𝑝a,b,p,求 𝑎𝑏 mod 𝑝abmodp。 输入格式 输入只有一行三个整数,分别代表 𝑎,𝑏,𝑝a,b,p。…...
YOLOv8实战无人机视角目标检测
本文采用YOLOv8作为核心算法框架,结合PyQt5构建用户界面,使用Python3进行开发。YOLOv8以其高效的实时检测能力,在多个目标检测任务中展现出卓越性能。本研究针对无人机目标数据集进行训练和优化,该数据集包含丰富的无人机目标图像…...
三、【docker】docker和docker-compose的常用命令
文章目录 一、docker常用命令1、镜像管理2、容器管理3、容器监控和调试4、网络管理5、数据卷管理6、系统维护7、实用组合命令8、常用技巧二、docker-compose常用命令1、基本命令2、构建相关3、运行维护4、常用组合命令5、实用参数 一、docker常用命令 1、镜像管理 # 查看本地…...
Qt 2D绘图之五:图形视图框架的结构、坐标系统和框架间的事件处理与传播
参考文章链接: Qt 2D绘图之五:图形视图框架的结构和坐标系统 Qt 2D绘图之六:图形视图框架的事件处理与传播 图形视图框架的结构 在前面讲的基本绘图中,我们可以自己绘制各种图形,并且控制它们。但是,如果需要同时绘制很多个相同或不同的图形,并且要控制它们的移动、…...
基于SpringBoot+Vue的美妆购物网站
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏:…...
MySQL之创建和管理表
目录 1. MySQL中的数据类型编辑编辑 2. 创建和管理数据库 方式1:创建数据库 方式2:创建数据库并指定字符集 方式3:判断数据库是否已经存在,不存在则创建数据库( 推荐 ) 总结 2.2 使用数据库 查看当…...
肌肉骨骼肿瘤治疗市场:潜力无限,未来可期
肌肉骨骼肿瘤治疗作为现代医学的重要分支,专注于应对骨骼和肌肉系统中的良性和恶性肿瘤。随着全球人口老龄化和生活方式的改变,肌肉骨骼疾病日益成为公共卫生的重要问题。与此同时,医疗技术的进步和患者对高质量医疗服务的需求不断推动该市场…...
QGIS 创建三维渲染动画
打开数据包中的denali工程文档,可以看到DEM图层和山体阴影图层。首先创建彩色的山体阴影效果: 接下来新建3D视图: 配置三维地图 配置后,可用鼠标中键、右侧的操作盘等进行三维旋转等操作。 接下来在三维地图中创建动画效果&#x…...
Vue生成类似于打卡页面
数据表格 <el-table :data"tableData" border height"calc(100vh - 240px)" :cell-style"cellFun"><el-table-column label"姓名" show-overflow-tooltip prop"name" align"center"/><el-table-co…...
软件工程——期末复习(2)
Part1:软件工程基本概念 软件程序文档数据 在软件工程中,软件通常被定为程序、文档和数据的集合。程序是按事先设计的功能和性能要求编写的指令序列;程序是完成指定功能的一段特定语言代码。文档是描述程序操作和使用的文档,是与…...
vxe-table 键盘操作,设置按键编辑方式,支持覆盖方式与追加方式
vxe-table 全键盘操作,按键编辑方式设置,覆盖方式与追加方式; 通过 keyboard-config.editMode 设置按键编辑方式;支持覆盖方式编辑和追加方式编辑 安装 npm install vxe-pc-ui4.3.15 vxe-table4.9.15// ... import VxeUI from v…...
【BUG】VMware|vmrest正在运行此虚拟机,无法配置或删除快照
VMware版本:VMware 16 文章目录 省流版问题解决方案 详细解释版问题解决方案总结 省流版 问题 只读,因为vmrest正在运行虚拟机。 解决方案 参考:虚拟机设置,只读,因为vmrest正在运行此虚拟机。有谁遇到过这种问题吗&…...
STM32 串口和I2C结合案例:
需求 1. 电脑通过串口 给单机 下发点灯计划 例如 13322 单片机上的灯 LED1 亮1秒 灭1秒 LED3 亮1秒 灭1秒 LED3 亮一秒 灭1秒 133221332213322-> mian.c #include "usart1.h" #include "M24C02.h" #include "stdio.h" #include "le…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...
Python学习(8) ----- Python的类与对象
Python 中的类(Class)与对象(Object)是面向对象编程(OOP)的核心。我们可以通过“类是模板,对象是实例”来理解它们的关系。 🧱 一句话理解: 类就像“图纸”,对…...
