算法分析,以4*4的方格为例,特殊方格只能在左上,右上,左下,右下四个区间中的一个。排列形式可能是如下几种
(1)特殊方格在左上区域,那么其他几个区域的特殊方格可定,一定分布方式如下,用1标识其他几个区域的特殊方格
(2)特殊方格在右上区域,那么其他几个区域的特殊方格可定,一定分布方式如下,用1标识其他几个区域的特殊方格
(3)特殊方格在左下区域,那么其他几个区域的特殊方格可定,一定分布方式如下,用1标识其他几个区域的特殊方格
(4)特殊方格在右下区域,那么其他几个区域的特殊方格可定,一定分布方式如下,用1标识其他几个区域的特殊方格
因此问题分解为特殊方格在一个区域,其余三个1分别变成三个不同区域的特殊方格,确定这三个方格的位置后,再分别对这四个区域进行递归解决子问题直到问题的解为最小解。
代码:
//棋盘覆盖问题,by lilywangcn
public class CheckBoard {
private static int size=3;
private static int edge=power(2,size);
private static int[][] board=new int[edge][edge];
private static int tile=1;
public static void main(String[] args){
int x=1;
int y=1;
board[x][y]=-1; //设置第x行,第y列为特殊方格
print();
checkboard(0,0,x,y,size);
System.out.println("after:");
print();
}
public static void checkboard(int tr, int tc, int dr,int dc, int size){
if(size==1) return ;
else{
size=size-1;
int edge=power(2,size);
if(dr<tr+edge&&dc<tc+edge){ //特殊方格在左上区域
checkboard(tr,tc,dr,dc,size);
}else{
board[tr+edge-1][tc+edge-1]=tile; //特殊方格不在左上区域,确定左上区域的特殊方格
checkboard(tr,tc,tr+edge-1,tc+edge-1,size);
}
//右上区域
if(dr<tr+edge&&dc>=tc+edge){
checkboard(tr,tc+edge,dr,dc,size);
}else{
board[tr+edge-1][tc+edge]=tile;
checkboard(tr,tc+edge,tr+edge-1,tc+edge,size);
}
//左下区域
if(dr>=tr+edge&& dc<tc+edge){
checkboard(tr+edge,tc,dc,dr,size);
}else{
board[tr+edge][tc+edge-1]=tile;
checkboard(tr+edge,tc,tr+edge,tc+edge-1,size);
}
//右下区域
if(dr>=tr+edge&& dc>=tc+edge){
checkboard(tr+edge,tc+edge,dc,dr,size);
}else{
board[tr+edge][tc+edge]=tile;
checkboard(tr+edge,tc+edge,tr+edge,tc+edge,size);
}
tile++;
// System.out.println("tile:" +tile);
// print();
}
}
private static void print(){
for(int i=0;i<edge;i++){
for(int j=0;j<edge;j++)
{
System.out.print(board[i][j]+ " ");
}
System.out.println("");
}
}
private static int power(int a,int o){
int result=1;
for(int i=0;i<o;i++)
result*=a;
return result;
}
}
运行结果:
size=2的时候:4*4=16
0 0 0 0
0 -1 0 0
0 0 0 0
0 0 0 0
after :
0 0 0 0
0 -1 1 0
0 1 1 0
0 0 0 0
size=3的时候:8*8=64;
0 0 0 0 0 0 0 0
0 -1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
after:
0 0 0 0 0 0 0 0
0 -1 1 0 0 2 2 0
0 1 1 0 0 0 2 0
0 0 0 0 2 0 0 0
0 0 0 3 4 0 0 0
0 3 0 0 0 0 4 0
0 3 3 0 0 4 4 0
0 0 0 0 0 0 0 0
- 大小: 179.9 KB
分享到:
相关推荐
这是我们校选课上的一个题目,利用分治算法去解棋盘覆盖问题算是最简单的办法吧。在还没加入校队前就看到过这个题目,当时真的有种没法入手,也许那时真的什么都不懂吧,根本也没想过到底怎么入手。自从加入校队,...
棋盘覆盖问题是递归的分治思想的典型应用,本文档利用c/c++ 实现棋盘覆盖问题
棋盘覆盖问题C++程序,运行成功,棋盘大小自己输入的
使用JAVA解决残缺棋盘覆盖问题:一个n*n的棋盘上有一个缺陷点,该点不能被覆盖,剩下的格子全部用三盒板覆盖。应用的是分治法。
C# vs2010 实现棋盘覆盖问题,有源代码,和讲义。
在一个2^k*2^k个方格组成的棋盘中,恰有一个方格与其他方格不同...棋盘覆盖问题要求下图四种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且任意2个L型骨牌不得重叠覆盖。 (仅供参考,请独立完成实验)
在一个2k*2k个方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格位一...在棋盘覆盖问题中,要用4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
c++ (分治法)棋盘覆盖问题实现 含有PPT 自己研究算法哟 可以运行
算法实践 棋盘覆盖问题_可视化 用MFC实现
棋盘覆盖问题是显示生活中的一个重要的应用,并且是可视化的,现在拿出来与大家分享哦
可视化实现算法设计棋盘覆盖问题 界面化的效果!!
棋盘覆盖问题 棋盘覆盖问题_基于Python实现棋盘覆盖问题
java_图形化界面-流水作业最优调度问题以及棋盘覆盖问题源码整理
棋盘覆盖问题 棋盘覆盖问题_基于C++实现的棋盘覆盖问题的归并解法
棋盘覆盖问题,MFC程序(VS2010平台) 包含源代码,可执行程序 还有一份算法说明 程序主要功能: 1、 可选棋盘大小 2、 鼠标选择或自动选择不覆盖块 3、 单步覆盖棋盘 4、 自动覆盖棋盘 5、 调整覆盖速度 声明:...