本文实例讲述了Java基于分治算法实现的棋盘覆盖问题。分享给大家供大家参考,具体如下:
在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖。四个L型骨牌如下图:
棋盘中的特殊方格如图:
实现的基本原理是将2^k * 2^k的棋盘分成四块2^(k - 1) * 2^(k - 1)的子棋盘,特殊方格一定在其中的一个子棋盘中,如果特殊方格在某一个子棋盘中,继续递归处理这个子棋盘,直到这个子棋盘中只有一个方格为止如果特殊方格不在某一个子棋盘中,将这个子棋盘中的相应的位置设为骨牌号,将这个无特殊方格的了棋盘转换为有特殊方格的子棋盘,然后再递归处理这个子棋盘。以上原理如图所示:
具体代码如下:
package demo; public class Chess { /*tr表示棋盘左上角行号 tc表示棋盘左上角列号 dr表示特殊棋盘的行号 dc表示特殊棋盘的列号*/ public static void ChessBoard(int tr, int tc, int dr, int dc, int size) { if(size == 1) { return; } int t = title ++; int s = size/2; //覆盖左上角子棋盘 if(dr= tc + s) { //特殊方格在此棋盘中 ChessBoard(tr, tc+s, dr, dc, s); } else {//此棋盘中午特殊方格,用t号L型骨牌覆盖左下角 Board[tr + s - 1][tc + s] = t; //覆盖其余方格 ChessBoard(tr, tc + s, tr + s - 1, tc + s, s); } //覆盖左下角子棋盘 if(dr >= tr + s && dc = tr + s && dc >= tc + s) { //特殊方格在此棋盘中 ChessBoard(tr + s, tc+s, dr, dc, s); } else {//此棋盘中无特殊方格,用t号L型骨牌覆盖左上角 Board[tr + s ][tc + s] = t; //覆盖其余方格 ChessBoard(tr + s, tc + s, tr + s , tc + s, s); } } @SuppressWarnings("static-access") public static void main(String args[]) { System.out.println("测试结果:"); Board[2][2] = 0; Chess ch = new Chess(); ch.ChessBoard(0, 0, 2, 2, size); for(int i = 0; i 运行结果:
更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。
写下你的评论吧 !推荐阅读
Mergeksortedlinkedlistsandreturnitasonesortedlist.Analyzeanddescribeitscomplexity.合并k个排序链表 ... [详细]蜡笔小新 2024-10-17 21:38:40 之前在命令行下面打印JSON的时候统统都是Cat,然后将结果复制到支持JSON解析的编辑器里面,非常曲折。简单的搜索了一下之后,在StackOverflow上找到了一篇文章。支持率 ... [详细]蜡笔小新 2024-10-17 21:04:17 #服务器程序自动化生成工具(Myide)##背景:目前互联网行业在中国飞速发展,万众创新,大众创业的浪潮中,对服务器程序开 ... [详细]蜡笔小新 2024-10-17 18:19:55 计算机学科领域复杂而广阔,学习过程漫长而多样,对学习对象的内容进行归类划分,形成不同阶段的学习内容,有利于高效学习ÿ ... [详细]蜡笔小新 2024-10-17 18:00:50 首页新闻列表正文发布时间:2020-11-0322:17:02浏览:37导读:素衣网络为您提供南浔区整合营销服务商,新闻营销的相关知识 ... [详细]蜡笔小新 2024-10-17 17:44:12 本文目录一览:1、北大青鸟java培训:Java集合框架的知识总结? ... [详细]蜡笔小新 2024-10-17 17:21:12 决策树(decisiontree)是一种常见的分类和回归算法,也是性能较好的提升树算法(boostingtree)的基本分类器。在分类问题中,决策树模型是以树的结构,基于特征来对样本进行分类决 ... [详细]蜡笔小新 2024-10-17 17:17:28 篇首语:本文由编程笔记#小编为大家整理,主要介绍了乐观锁VS悲观锁相关的知识,希望对你有一定的参考价值。 ... [详细]蜡笔小新 2024-10-17 17:13:15 这段代码我可以跟你解释,是个经典代码了,刚好我也刚看过,我这是长这个样子的:defchecksum(data):iflen( ... [详细]蜡笔小新 2024-10-17 16:08:07 针对此次要解决的问题,现象如下图所示:这个问题出现在预装正版win10操作系统时,这个需要进“安全模式“”中进行修复。具体步骤如下:1、开机出现LOGO界面长按电源键关机,连续两次 ... [详细]蜡笔小新 2024-10-17 15:47:02 参考自:跳转HashMap和LinkedHashMap属于线程不安全的HashTable属于线程安全再来看看HashMap和LinkedHashMap的结构图 ... [详细]蜡笔小新 2024-10-17 15:21:07 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算 ... [详细]蜡笔小新 2024-10-17 13:34:29 网络爬虫分为两类1.通用爬虫:类似于baidu,google.他们会把大量的数据挖下来,保存到自己的服务器上.用户打开跳转的时候,其实先是跳转到他们自己的服务器. 2.聚焦爬虫: ... [详细]蜡笔小新 2024-10-17 12:45:37 宝宝贝贝198812126这个家伙很懒,什么也没留下!RankList | 热门文章
- 1C++课程学习笔记第五周:继承
- 2fix: don't ship an Ivy compiled library
- 3Python3+Appium安装使用教程
- 4持续集成学习总结(一)
- 5jq跨域代理_基于jQuery的AJAX跨域问题完美解决方案[转]
- 6xshell连接linux中vim小键盘的问题解决
- 7A4Desk 网站破解
- 8Java 程序以上午下午格式格式化时间
- 9weigh比例布局
- 10react native 调试下良好,打包之后 tabview中initpage webview无法显示出来?
- 11win7不识别u盘怎么办?
- 12渡鸦科技进军智能家居硬件
- 13开发笔记:Apache Commons:简单的使用Compress创建7z压缩文件
- 14如何运用百度地图SDK进行开发(一)初级篇
- 15Beta 第五天
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有