admin 管理员组文章数量: 893893
分治法——棋盘覆盖问题/L形组件填图问题(Java实现)
问题描述
设B是一个n×n棋盘,n=2k,(k=1,2,3,…)。用分治法设计一个算法,使得:用若干个L型条块可以覆盖住B的除一个特殊方格外的所有方格。其中,一个L型条块可以覆盖3个方格。且任意两个L型条块不能重叠覆盖棋盘。
例如:如果n=2,则存在4个方格,其中,除一个方格外,其余3个方格可被一L型条块覆盖;当n=4时,则存在16个方格,其中,除一个方格外,其余15个方格被5个L型条块覆盖。
具体要求
输入一个正整数n,表示棋盘的大小是n*n的。输出一个被L型条块覆盖的n*n棋盘。该棋盘除一个方格外,其余各方格都被L型条块覆盖住。为区别出各个方格是被哪个L型条块所覆盖,每个L型条块用不同的数字或颜色、标记表示。
测试数据
输入:8
输出:
解题思路
分治法
(一)什么是分治法
要想使用分治法解决此问题,我们就先需要了解一下什么是分治法。
分治法,简单来说,就是把一个问题不断地切分成与原问题性质相同、规模更小的子问题,直到子问题的规模足够小到可以直接求解,然后将子问题的解组合起来,得到原问题的解。
(二)分治法的一般解题步骤
由于分治法本身的递归特性,一般用递归实现分治算法。
分治法解题往往采用递归的方法实现,在递归求解子问题时同样要注意理清递归关系、递归出口、参数设置等问题。
最后,通过组合子问题形成原问题的解。
问题分析
面对L形组件填图问题,第一步我们需要思考如何划分
一个n * n的棋盘,我们可以想到有下面几种划分方式
我们可以看到,前两种划分会造成一个问题:划分后的子棋盘变成了长方形,而原问题是一个n * n的正方形,导致子问题性质和原问题性质不一样
所以,应采用第三种划分方式。
但这样子问题的性质就和原问题性质一样了吗?
注意,我们原问题所在的棋盘是有一个特殊方块(或者说是残缺方块),将原来的棋盘划分成四个子棋盘后,其中的一个子棋盘仍有特殊方块,但剩下的三个子棋盘没有特殊方块!
那如何使剩下的三个子棋盘都有特殊方块呢?
我们可以刚好依照问题要求,使用L形条块进行填充,作为该子棋盘的特殊方块,使得子问题与原问题性质相同
如此之后,我们就可以使用递归,求解问题
代码实现
棋盘表示
我们使用二维整型数组表示棋盘,使用数字(1、2、3....)进行填充,用0表示原问题的特殊方块(残缺方块)
区分四种棋盘
划分以后,我们会出现下面四种情况
如何区分四个子棋盘,以及如何区分特殊方块在哪一个子棋盘(左上、右上、左下、右下)中呢?
我们利用棋盘左上角的坐标和原棋盘大小(leftRow、leftCol、size)来标识一个棋盘
用specialRow、specialCol来表示特殊方块(残缺格)的位置
如果特殊方块在左上的子棋盘中
即specialRow < leftRow + size/2 && specialCol < leftCol + size/2
第一步:递归该子棋盘
第二步:填充L型组件(即填充图中的蓝色方块)
第三步:递归其他三个子棋盘
如果特殊方块在右上的子棋盘中
即specialRow < leftRow + size/2 && specialCol > leftCol + size/2
....(同上)
如果特殊方块在左下的子棋盘中
即specialRow > leftRow + size/2 && specialCol < leftCol + size/2
...(同上)
如果特殊方块在右下的子棋盘中
即specialRow > leftRow + size/2 && specialCol > leftCol + size/2
...(同上)
具体代码(java)
import java.util.Arrays;
import java.util.Scanner;public class Test1 {static int size;//棋盘大小static int[][] arr;//表示棋盘static int count = 1;//定义一个静态count用于填充public static void main(String[] args) {//1.接收参数nScanner sc = new Scanner(System.in);size = sc.nextInt();//2.创建n*n大小的二维数组arr = new int[size][size];//3.随机指定某一个位置为特殊方块(暂时假设第一行第一个元素为特殊方块)arr[0][0] = 0;Cover(0,0,0,0,size);Output(size);}//4.定义解决问题的函数public static void Cover(int leftRow,int leftCol,int specialRow,int specialCol,int size){//出口if(size < 2){return;}count++;int flag = count;//如果特殊方块在左上子棋盘if(specialRow < leftRow + size/2 && specialCol < leftCol + size/2){//递归覆盖该子棋盘Cover(leftRow,leftCol,specialRow,specialCol,size/2);//使得剩余的三个子棋盘性质与原问题相同arr[leftRow + size/2 - 1][leftCol + size/2] = flag;//填充右上子棋盘左下角arr[leftRow + size/2][leftCol + size/2 - 1] = flag;//填充左下子棋盘右上角arr[leftRow + size/2][leftCol + size/2] = flag;//填充右下棋盘左上角//递归覆盖三个子棋盘Cover(leftRow,leftCol+size/2,leftRow + size/2 - 1, leftCol + size/2,size/2);//右上子棋盘Cover(leftRow + size/2,leftCol,leftRow + size/2,leftCol + size/2 - 1,size/2);//左下子棋盘Cover(leftRow + size/2,leftCol + size/2,leftRow + size/2,leftCol + size/2,size/2);//右下子棋盘}else if(specialRow < leftRow + size/2 && specialCol >= leftCol + size/2){//如果特殊方块在右上子棋盘Cover(leftRow,leftCol + size/2,specialRow,specialCol,size/2);arr[leftRow + size/2 - 1][leftCol + size/2 - 1] = flag;//填充左上子棋盘右下角arr[leftRow + size/2][leftCol + size/2 - 1] = flag;//填充左下子棋盘右上角arr[leftRow + size/2][leftCol + size/2] = flag;//填充右下棋盘左上角Cover(leftRow,leftCol,leftRow + size/2 - 1, leftCol + size/2 - 1,size/2);//左上子棋盘Cover(leftRow + size/2,leftCol,leftRow + size/2,leftCol + size/2 - 1,size/2);//左下子棋盘Cover(leftRow + size/2,leftCol + size/2,leftRow + size/2,leftCol + size/2,size/2);//右下子棋盘}else if(specialRow >= leftRow + size/2 && specialCol < leftCol + size/2){//如果特殊方块在左下子棋盘Cover(leftRow + size/2,leftCol,specialRow,specialCol,size/2);arr[leftRow + size/2 - 1][leftCol + size/2 - 1] = flag;//填充左上子棋盘右下角arr[leftRow + size/2 - 1][leftCol + size/2] = flag;//填充右上子棋盘左下角arr[leftRow + size/2][leftCol + size/2] = flag;//填充右下棋盘左上角Cover(leftRow,leftCol,leftRow + size/2 - 1, leftCol + size/2 - 1,size/2);//左上子棋盘Cover(leftRow,leftCol+size/2,leftRow + size/2 - 1, leftCol + size/2,size/2);//右上子棋盘Cover(leftRow + size/2,leftCol + size/2,leftRow + size/2,leftCol + size/2,size/2);//右下子棋盘}else if(specialRow >= leftRow + size/2 && specialCol >= leftCol + size/2){//如果特殊方块在右下子棋盘Cover(leftRow + size/2,leftCol + size/2,specialRow,specialCol,size/2);arr[leftRow + size/2 - 1][leftCol + size/2 - 1] = flag;//填充左上子棋盘左下角arr[leftRow + size/2 - 1][leftCol + size/2] = flag;//填充右上子棋盘左下角arr[leftRow + size/2][leftCol + size/2 - 1] = flag;//填充左下子棋盘右上角Cover(leftRow,leftCol+size/2,leftRow + size/2 - 1, leftCol + size/2,size/2);//右上子棋盘Cover(leftRow + size/2,leftCol,leftRow + size/2,leftCol + size/2 - 1,size/2);//左下子棋盘Cover(leftRow + size/2,leftCol + size/2,leftRow + size/2,leftCol + size/2,size/2);//右下子棋盘}}public static void Output(int size){for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {System.out.print(arr[i][j] + "\t");}System.out.println("");}}
}
运行结果
今天的内容就介绍到这啦,若对你有帮助的话就点个赞👍吧~
关注博主,宝藏多多~
本文标签: 分治法棋盘覆盖问题L形组件填图问题(Java实现)
版权声明:本文标题:分治法——棋盘覆盖问题L形组件填图问题(Java实现) 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1687604043h120123.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论