利用分治策略实现棋盘覆盖（C语言）

问题描述：

在一个由  ✖个方格组成的棋盘中，有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。要求使用不同形态的L型骨牌（四种）覆盖给定的棋盘上除特殊方格以外的所有方格，且骨牌之间不能重叠。

概要设计：

第一步：划分问题，将   ✖个方格组成的棋盘棋盘划分为 4块  ✖ 个方格组成的棋盘。  

先思考一下k=2时候，能不能把大棋盘分成更小的棋盘？

 现在的问题是：原问题与子问题不同。特殊方格位于其中一个小棋盘中，其余3个子棋盘中无特殊方格，为将这3个无特殊方格的子棋盘转为特殊盘，可用一个骨牌覆盖这3个子棋盘的汇合处。3个子棋盘上被骨牌覆盖的方格就成为该子棋盘的特殊方格从而将原问题化为4个较小规模的子问题。

第二步：递归求解，一个函数分四种情况：（左上，不在）递归填充各个格子，填充分为四个情况。

第三步：合并问题，可以说本实验不需要合并子问题。

详细设计：

#include
int title=1;
int board[100][100]={0};
void  chess (int h0 , int l0 ,int th ,int tl ,int size )
{
	if (size==1) return;
	int t=++title;
	int s=size/2;
	
	//判断左上 
	if(th<=h0+s-1&&tl<=l0+s-1)
	//在左上就直接调函数求解 
	chess(h0,l0,th,tl,s);
	else
	//不再左上 就把左上的右下格置为t 
{
		board[h0+s-1][l0+s-1]=t;
	//左上就有特殊方格啦 可以直接递归调用 
	chess(h0,l0,h0+s-1,l0+s-1,s);
}
	//判断右上
	if(th<=h0+s-1&&tl>=l0+s)
	chess(h0,l0+s,th,tl,s);
	else
{
		board[h0+s-1][l0+s]=t;
	//将右上添加一个特殊方格之后 右上部分的左上角就是再次调用函数的第一组参数 
	chess(h0,l0+s,h0+s-1,l0+s,s);
}	
	//判断左下
	 if(th>=h0+s&&tl<=l0+s-1)
	chess(h0+s,l0,th,tl,s);
	else
	//将左下的右上置为t 
{	board[h0+s][l0+s-1]=t;
	chess(h0+s,l0,h0+s,l0+s-1,s);
}
	//判断右下
	if(th>=h0+s&&tl>=l0+s)
	chess(h0+s,l0+s,th,tl,s);
	else
{
	board[h0+s][l0+s]=t;
	chess(h0+s,l0+s,h0+s,l0+s,s); 
}
 } 

int main()
{
	int x,y,size1;
	
while(1)
{
		printf("输入棋盘大小size= (size是2的n次方|n是整数)：\n");
		scanf("%d",&size1);	
		printf("输入特殊方格的坐标:\n");
		scanf("%d %d",&x,&y);
		chess(0,0,x,y,size1);
		//输出棋盘
		for(int i=0;i

运行结果：

 

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/872712.html