本文为原创,如需转载,请注明作者和出处,谢谢! 在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖。
四各L型骨牌如下图1
图1
棋盘中的特殊方格如图2
图2
实现的基本原理是将2^k * 2^k的棋盘分成四块2^(k - 1) * 2^(k -
1)的子棋盘,特殊方格一定在其中的一个子棋盘中,如果特殊方格在某一个子棋盘中,继续递归处理这个子棋盘,直到这个子棋盘中只有一个方格为止如果特殊方
格不在某一个子棋盘中,将这个子棋盘中的相应的位置设为骨牌号,将这个无特殊方格的了棋盘转换为有特殊方格的子棋盘,然后再递归处理这个子棋盘。以上原理
如图3所示。
图3
将棋盘保存在一个二维数组中。骨牌号从1开始,特殊方格为0,如果是一个4 * 4的棋盘,特殊方格为(2,2),那么程序的输出为
2 2 3 3
2 1 1 3
4 1 0 5
4 4 5 5
相同数字的为同一骨牌。
下面是棋盘覆盖问题的c语言实现。
<!--<br />
<br />
Code highlighting produced by Actipro CodeHighlighter (freeware)<br />
http://www.CodeHighlighter.com/<br />
<br />
-->#include<stdio.h>
#defineBOARD_SIZE4
intboard[BOARD_SIZE][BOARD_SIZE];
//c1,r1:棋盘左上角的行号和列号
//c2,r2:特殊方格的行号和列号
//size=2^k
voidchessboard(intr1,intc1,intr2,intc2,intsize)
{
if(1==size)return;
inthalf_size;
staticintdomino_num=1;
intd=domino_num++;
half_size=size/2;
if(r2<r1+half_size&&c2<c1+half_size)//特殊方格在左上角子棋盘
{
chessboard(r1,c1,r2,c2,half_size);
}
else//不在此棋盘,将此棋盘右下角设为相应的骨牌号
{
board[r1+half_size-1][c1+half_size-1]=d;
chessboard(r1,c1,r1+half_size-1,c1+half_size-1,half_size);
}
if(r2<r1+half_size&&c2>=c1+half_size)//特殊方格在右上角子棋盘
{
chessboard(r1,c1+half_size,r2,c2,half_size);
}
else//不在此棋盘,将此棋盘左下角设为相应的骨牌号
{
board[r1+half_size-1][c1+half_size]=d;
chessboard(r1,c1+half_size,r1+half_size-1,c1+half_size,half_size);
}
if(r2>=r1+half_size&&c2<c1+half_size)//特殊方格在左下角子棋盘
{
chessboard(r1+half_size,c1,r2,c2,half_size);
}
else//不在此棋盘,将此棋盘右上角设为相应的骨牌号
{
board[r1+half_size][c1+half_size-1]=d;
chessboard(r1+half_size,c1,r1+half_size,c1+half_size-1,half_size);
}
if(r2>=r1+half_size&&c2>=c1+half_size)//特殊方格在左上角子棋盘
{
chessboard(r1+half_size,c1+half_size,r2,c2,half_size);
}
else//不在此棋盘,将此棋盘左上角设为相应的骨牌号
{
board[r1+half_size][c1+half_size]=d;
chessboard(r1+half_size,c1+half_size,r1+half_size,c1+half_size,half_size);
}
}
intmain()
{
inti,j;
board[2][2]=0;
chessboard(0,0,2,2,BOARD_SIZE);
for(i=0;i<BOARD_SIZE;i++)
{
for(j=0;j<BOARD_SIZE;j++)
{
printf("%-4d",board[i][j]);
}
printf("\n");
}
}
国内最棒的Google Android技术社区(eoeandroid),欢迎访问!《银河系列原创教程》发布《Java Web开发速学宝典》出版,欢迎定购
分享到:
相关推荐
C++实现的棋盘覆盖算法 经典算法之一 对初学算法者帮助很大
棋盘覆盖问题是递归的分治思想的典型应用,本文档利用c/c++ 实现棋盘覆盖问题
主要介绍了Java基于分治算法实现的棋盘覆盖问题,简单描述了棋盘覆盖问题,并结合具体实例形式分析了java基于分治算法实现棋盘覆盖问题的相关操作技巧,需要的朋友可以参考下
老师上课讲的内容 棋盘覆盖的具体算法实现 觉得蛮有用 的跟大家分享
利用MFC实现棋盘算法的演示,分治法进行棋盘覆盖问题的演示。
棋盘覆盖方块版输出Java和棋盘覆盖数字版输出Java 问题描述 ...在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
棋盘覆盖算法实现,希望对大家有用,可以拿去参看参考!
C++ 算法分析与设计 分治法实现棋盘覆盖问题
分治法解决棋盘覆盖与二分查找问题,C++描述.算法设计与分析经典例题
可视化实现算法设计棋盘覆盖问题 界面化的效果!!
实现有面板,可输入边值然后根据边值生成棋盘。
c++ (分治法)棋盘覆盖问题实现 含有PPT 自己研究算法哟 可以运行
摘要:在本次棋盘覆盖算法设计过程中,要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。为解决此类问题,采用了分治算法来减小问题规模从而逐步求解问题来...
棋盘覆盖(c语言实现)
棋盘覆盖问题,MFC程序(VS2010平台) 包含源代码,可执行程序 还有一份算法说明 程序主要功能: 1、 可选棋盘大小 2、 鼠标选择或自动选择不覆盖块 3、 单步覆盖棋盘 4、 自动覆盖棋盘 5、 调整覆盖速度 声明:...
在棋盘覆盖问题中,要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 当k>0时,将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘,特殊方格必位于4个较小子棋盘之一...
棋盘覆盖问题 使用归并算法来解决棋盘覆盖问题_基于C++实现
程序中主要描述了棋盘覆盖的分治算法。实际的应用中只是利用这种思想。例如分型的经典模型就和这个例子很相像。
算法分析里的棋盘覆盖问题,VC编程实现,是基于图形界面的,能很好的演示。附带有算法的实验报告
编译器:Microsoft Visual Studio 2008 实现功能:棋盘覆盖算法的图形展示。 涉及知识:定时器、STL、基本MFC画图API、双缓冲贴图 推荐资料:孙鑫的VC++ 深入详解