Java基于分治算法实现的棋盘覆盖问题示例
作者:萌神哆啦A梦 时间:2021-07-17 14:05:16
本文实例讲述了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 < tr + s && dc < tc +s) {
//特殊方格在此棋盘中
ChessBoard(tr, tc, dr, dc, s);
}
else {
//此棋盘中无特殊方格,用t号L型骨牌覆盖右下角
Board[tr + s - 1][tr + s -1] = t;
//覆盖其余方格
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 {//此棋盘中午特殊方格,用t号L型骨牌覆盖左下角
Board[tr + s - 1][tc + s] = t;
//覆盖其余方格
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 {
//此棋盘中无特殊方格,用t号L型骨牌覆盖右上角
Board[tr + s][tr + s -1] = t;
//覆盖其余方格
ChessBoard(tr, tc, tr + s , tc + s - 1, s);
}
//覆盖右下角子棋盘
if(dr >= 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 < size; ++ i) {
for(int j = 0; j < size; j++) {
System.out.print(Board[i][j] + " ");
}
System.out.println();
}
}
static final int size = 4;
static int title = 1;
static int Board[][] = new int[size][size];
}
运行结果:
希望本文所述对大家java程序设计有所帮助。
来源:http://blog.csdn.net/u014755255/article/details/50531621
标签:Java,分治算法,棋盘覆盖
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
利用Java简单实现一个代码行数统计器方法实例
2023-01-12 10:50:25
![](https://img.aspxhome.com/file/2023/0/79860_0s.png)
Java针对ArrayList自定义排序的2种实现方法
2022-01-30 03:47:34
Java开发人员需知的十大戒律
2023-09-17 07:33:50
高斯混合模型与EM算法图文详解
2022-10-02 12:05:02
![](https://img.aspxhome.com/file/2023/5/61855_0s.jpg)
java抓取网页或文件中的邮箱号码
2023-07-30 19:19:28
![](https://img.aspxhome.com/file/2023/9/62119_0s.jpg)
SpringBoot2之PUT请求接收不了参数的解决方案
2023-08-23 01:32:07
![](https://img.aspxhome.com/file/2023/2/58202_0s.png)
Mybatis使用JSONObject接收数据库查询的方法
2023-01-17 05:10:43
![](https://img.aspxhome.com/file/2023/7/62647_0s.png)
SpringBoot上传临时文件被删除引起报错的解决
2022-05-28 23:46:24
![](https://img.aspxhome.com/file/2023/6/74886_0s.jpg)
Spring Data Jpa框架最佳实践示例
2021-11-25 00:43:01
详解Spring与Mybatis整合方法(基于IDEA中的Maven整合)
2023-11-06 21:35:12
![](https://img.aspxhome.com/file/2023/0/58690_0s.png)
C#推送信息到APNs的方法
2023-05-29 05:20:59
浅试仿 mapstruct实现微服务编排框架详解
2022-07-12 13:20:44
![](https://img.aspxhome.com/file/2023/0/63420_0s.png)
SpringCloud Function SpEL注入漏洞分析及环境搭建
2022-07-03 05:18:21
![](https://img.aspxhome.com/file/2023/9/70949_0s.png)
springboot之如何获取项目目录路径
2022-08-09 21:44:17
![](https://img.aspxhome.com/file/2023/6/60796_0s.jpg)
SpringBoot持久化层操作支持技巧
2023-11-24 06:40:32
![](https://img.aspxhome.com/file/2023/3/59933_0s.png)
详解Java中Callable和Future的区别
2023-07-25 21:18:58
![](https://img.aspxhome.com/file/2023/8/63038_0s.jpg)
elasticsearch集群cluster示例详解
2023-12-11 16:49:27
![](https://img.aspxhome.com/file/2023/3/67003_0s.png)
JVM内存增强之逃逸分析
2022-01-23 00:22:08
Mybatis 复杂对象resultMap的使用
2023-10-12 22:56:44
![](https://img.aspxhome.com/file/2023/7/58557_0s.png)
详解APP微信支付(java后台_统一下单和回调)
2023-11-10 17:26:42
![](https://img.aspxhome.com/file/2023/3/59153_0s.png)