C语言【微项目10】—棋盘覆盖问题[递归到基本四格单位时填充]（采用分治法实现）

目录
  • 一、MyCoverBoardA.c
  • 二、 MyCoverBoardB.c
  • MyCoverBoardA.c-运行结果示例
    • 1.k为1
      •    1.1缺陷在1 0位置
      •    1.2缺陷在0 0位置
    • 2.k为2
      •    2.1缺陷在1 2位置
      •    2.2缺陷在2 3位置
    • 3.k为3
      •    3.1缺陷在5 6位置
      •    3.1缺陷在4 2位置
    • 4.k为4
      • 4.1   3.1缺陷在12 9位置
  • MyCoverBoardB.c-运行结果示例
    • 1.k为1
      •    1.2缺陷在0 0位置
      •    1.1缺陷在0 1位置
      •    1.1缺陷在1 0位置
      •    1.2缺陷在1 1位置
    • 2.k为2
      •    2.1缺陷在1 2位置
      •    2.2缺陷在2 3位置
    • 3.k为3
      •    3.1缺陷在5 6位置
      •    3.1缺陷在4 2位置
    • 4.k为4
      • 4.1   3.1缺陷在12 9位置

【TDTX】
【MyCoverBoardA.c】把棋盘的填充视为：【排除缺陷式】位置填充；
【MyCoverBoardB.c】把棋盘的填充视为：【图形卡位式】位置填充；
【总结】两者最终的结果完全相同，但视觉效果不同。

一、MyCoverBoardA.c

#include 
#include 
int qa,qb;
int mpow(int n,int k)
{
	int i;
	int t = n;
	for(i = 1; i < k;i++)
	{
		t = t * n;
	}
	return t;
}
void generateBoard(int tr,int tc,int dr,int dc,int size,int** b,int* t1)
{
	int hs = size / 2;
	if(size == 2)
	{
		if( dr == tr && dc == tc )
		{
			//残缺位置在4格左上角 
			b[tr][tc+1] = *t1;
			b[tr+1][tc] = *t1;
			b[tr+1][tc+1] = *t1;
			(*t1)++; 
		}
		if( dr== tr && dc == tc + 1)
		{
			//残缺位置在4格右上角 
			b[tr][tc] = *t1;
			b[tr+1][tc] = *t1;
			b[tr+1][tc+1] = *t1;
			(*t1)++; 
		}
		if( dr == tr + 1 && dc == tc)
		{
			//残缺位置在4格左下角 
			b[tr][tc] = *t1;
			b[tr][tc+1] = *t1;
			b[tr+1][tc+1] = *t1;	
			(*t1)++; 
		}
		if( dr == tr + 1 && dc == tc +1)
		{
			//残缺位置在4格右下角 
			b[tr][tc] = *t1;
			b[tr][tc+1] = *t1;
			b[tr+1][tc] = *t1;
			(*t1)++; 	
		}
/*
		for(int i = 0;i < 2*size;i++)
		{
			for(int j = 0;j < 2*size;j++)
			{
				printf("%d\t",b[i][j]); 
			}
			puts("");
		}
*/
		//printf("\ntr:%d,tc:%d----------------------\n",tr,tc);
		b[qa][qb] = 0;
		return;
	}
	else
	{
		if(dr < tr + hs && dc < tc + hs)
		{
			int tdr,tdc;
			//残缺在第二象限
			b[tr+hs-1][tc+hs] = *t1;
			b[tr+hs][tc+hs-1] = *t1;
			b[tr+hs][tc+hs] = *t1;
			(*t1)++; 
			generateBoard(tr,tc,dr,dc,hs,b,t1);
			
			tdr = tr + hs - 1;
			tdc = tc + hs; 
			generateBoard(tr,tc+hs,tdr,tdc,hs,b,t1);
			
			tdr = tr + hs;
			tdc = tc + hs - 1; 
			generateBoard(tr+hs,tc,tdr,tdc,hs,b,t1);
			
			tdr = tr + hs;
			tdc = tc + hs; 
			generateBoard(tr+hs,tc+hs,tdr,tdc,hs,b,t1);
		}
		if(dr < tr + hs && dc >= tc + hs)
		{
			int tdr,tdc;
			//残缺在第一象限
			b[tr+hs-1][tc+hs-1] = *t1;
			b[tr+hs][tc+hs-1] = *t1;
			b[tr+hs][tc+hs] = *t1;
			(*t1)++; 
			generateBoard(tr,tc+hs,dr,dc,hs,b,t1);
			
			tdr = tr + hs - 1;
			tdc = tc + hs - 1; 
			generateBoard(tr,tc,tdr,tdc,hs,b,t1);
			
			tdr = tr + hs;
			tdc = tc + hs - 1; 
			generateBoard(tr+hs,tc,tdr,tdc,hs,b,t1);

			tdr = tr + hs;
			tdc = tc + hs; 
			generateBoard(tr+hs,tc+hs,tdr,tdc,hs,b,t1);
		}
		if(dr >= tr + hs && dc < tc + hs)
		{
			int tdr,tdc;
			//残缺在第三象限
			b[tr+hs-1][tc+hs-1] = *t1;
			b[tr+hs-1][tc+hs] = *t1;
			b[tr+hs][tc+hs] = *t1;
			(*t1)++; 
			generateBoard(tr+hs,tc,dr,dc,hs,b,t1);
			
			tdr = tr + hs - 1;
			tdc = tc + hs - 1; 
			generateBoard(tr,tc,tdr,tdc,hs,b,t1);

			tdr = tr + hs - 1;
			tdc = tc + hs; 
			generateBoard(tr,tc+hs,tdr,tdc,hs,b,t1);
			
			tdr = tr + hs;
			tdc = tc + hs; 
			generateBoard(tr+hs,tc+hs,tdr,tdc,hs,b,t1);
		}
		if(dr >= tr + hs && dc >= tc + hs)
		{
			int tdr,tdc;
			//残缺在第四象限
			b[tr+hs-1][tc+hs-1] = *t1;
			b[tr+hs-1][tc+hs] = *t1;
			b[tr+hs][tc+hs-1] = *t1;
			(*t1)++; 
			generateBoard(tr+hs,tc+hs,dr,dc,hs,b,t1);
			
			tdr = tr+hs-1;
			tdc = tc+hs-1;
			generateBoard(tr,tc,tdr,tdc,hs,b,t1);
			
			tdr = tr+hs-1;
			tdc = tc+hs;
			generateBoard(tr,tc+hs,tdr,tdc,hs,b,t1);
			
			tdr = tr+hs;
			tdc = tc+hs-1;
			generateBoard(tr+hs,tc,tdr,tdc,hs,b,t1);
		}
	} 
}
int main()
{
	//左下残缺 右下残缺 左上残缺 右上残缺
	//* *      * *        *      *
	//  *      *        * *      * *
	
	int k;
	printf("输入棋盘2^k×2^k的k值：");
	scanf("%d",&k);
	int size = mpow(2,k);
	//printf("size = %d\n",size);
	
	int *b[size]; //生成棋盘矩阵
	for(int i = 0;i < size;i++)
	{
		b[i] = (int*)malloc(sizeof(int)*size);
	}
	for(int i = 0;i < size;i++)
	{
		for(int j = 0;j < size;j++)
		{
			b[i][j] = -1;
		}
		//puts("");
	}
	
	printf("输入残缺位置（行 列）：");
	scanf("%d %d",&qa,&qb);
	int dr,dc;
	dr = qa;
	dc = qb;
	int t1 = 1;
	
	if((qa < size && qa >= 0) && (qb < size && qb >= 0))
	{
		b[qa][qb] = 0;
		generateBoard(0,0,dr,dc,size,b,&t1);
		
		for(int i = 0;i < size;i++)
		{
			for(int j = 0;j < size;j++)
			{
				printf("%2d  ",b[i][j]); 
			}
			puts("");
		}
	}
	else
	{
		printf("残缺位置不在棋盘上，位置不合法！");
	}
	for(int i = 0;i < size;i++)
	{
		free(b[i]);
	}
	system("pause");
	return 0;
}

二、 MyCoverBoardB.c

#include 
#include 
#include 
int qa,qb;
int mpow(int n,int k)
{
	int i;
	int t = n;
	for(i = 1; i < k;i++)
	{
		t = t * n;
	}
	return t;
}
void generateBoard(int tr,int tc,int dr,int dc,int size,int** b)
{
	int hs = size / 2;
	if(size == 2)
	{
		if( dr == tr && dc == tc )
		{
			//残缺位置在4格左上角 
			//用3号覆盖
			b[tr][tc+1] = 3;
			b[tr+1][tc] = 3;
			b[tr+1][tc+1] = 3;
		}
		if( dr== tr && dc == tc + 1)
		{
			//残缺位置在4格右上角 
			//用4号覆盖
			b[tr][tc] = 4;
			b[tr+1][tc] = 4;
			b[tr+1][tc+1] = 4;
		}
		if( dr == tr + 1 && dc == tc)
		{
			//残缺位置在4格左下角 
			//用1号覆盖
			b[tr][tc] = 1;
			b[tr][tc+1] = 1;
			b[tr+1][tc+1] = 1;	
		}
		if( dr == tr + 1 && dc == tc +1)
		{
			//残缺位置在4格右下角 
			//用2号覆盖
			b[tr][tc] = 2;
			b[tr][tc+1] = 2;
			b[tr+1][tc] = 2;	
		}
/*
		for(int i = 0;i < 2*size;i++)
		{
			for(int j = 0;j < 2*size;j++)
			{
				printf("%d\t",b[i][j]); 
			}
			puts("");
		}
*/
		//printf("\ntr:%d,tc:%d----------------------\n",tr,tc);
		b[qa][qb] = 0;
		return;
	}
	else
	{
		if(dr < tr + hs && dc < tc + hs)
		{
			int tdr,tdc;
			//残缺在第二象限
			b[tr+hs-1][tc+hs] = 3;
			b[tr+hs][tc+hs-1] = 3;
			b[tr+hs][tc+hs] = 3;
	
			generateBoard(tr,tc,dr,dc,hs,b);
			
			tdr = tr + hs - 1;
			tdc = tc + hs; 
			generateBoard(tr,tc+hs,tdr,tdc,hs,b);
			
			tdr = tr + hs;
			tdc = tc + hs - 1; 
			generateBoard(tr+hs,tc,tdr,tdc,hs,b);
			
			tdr = tr + hs;
			tdc = tc + hs; 
			generateBoard(tr+hs,tc+hs,tdr,tdc,hs,b);
			
		}
		if(dr < tr + hs && dc >= tc + hs)
		{
			int tdr,tdc;
			//残缺在第一象限
			b[tr+hs-1][tc+hs-1] = 4;
			b[tr+hs][tc+hs-1] = 4;
			b[tr+hs][tc+hs] = 4;
			generateBoard(tr,tc+hs,dr,dc,hs,b);
			
			tdr = tr + hs - 1;
			tdc = tc + hs - 1; 
			generateBoard(tr,tc,tdr,tdc,hs,b);
			//generateBoard(tr,tc+hs,dr,dc,hs,b);
			
			tdr = tr + hs;
			tdc = tc + hs - 1; 
			generateBoard(tr+hs,tc,tdr,tdc,hs,b);

			tdr = tr + hs;
			tdc = tc + hs; 
			generateBoard(tr+hs,tc+hs,tdr,tdc,hs,b);
		}
		if(dr >= tr + hs && dc < tc + hs)
		{
			int tdr,tdc;
			//残缺在第三象限
			b[tr+hs-1][tc+hs-1] = 1;
			b[tr+hs-1][tc+hs] = 1;
			b[tr+hs][tc+hs] = 1;
			generateBoard(tr+hs,tc,dr,dc,hs,b);
			
			tdr = tr + hs - 1;
			tdc = tc + hs - 1; 
			generateBoard(tr,tc,tdr,tdc,hs,b);

			tdr = tr + hs - 1;
			tdc = tc + hs; 
			generateBoard(tr,tc+hs,tdr,tdc,hs,b);
			//generateBoard(tr+hs,tc,dr,dc,hs,b);
			
			tdr = tr + hs;
			tdc = tc + hs; 
			generateBoard(tr+hs,tc+hs,tdr,tdc,hs,b);
		}
		if(dr >= tr + hs && dc >= tc + hs)
		{
			int tdr,tdc;
			//残缺在第四象限
			b[tr+hs-1][tc+hs-1] = 2;
			b[tr+hs-1][tc+hs] = 2;
			b[tr+hs][tc+hs-1] = 2;
			generateBoard(tr+hs,tc+hs,dr,dc,hs,b);
			
			tdr = tr+hs-1;
			tdc = tc+hs-1;
			generateBoard(tr,tc,tdr,tdc,hs,b);
			
			tdr = tr+hs-1;
			tdc = tc+hs;
			generateBoard(tr,tc+hs,tdr,tdc,hs,b);
			
			tdr = tr+hs;
			tdc = tc+hs-1;
			generateBoard(tr+hs,tc,tdr,tdc,hs,b);
			//generateBoard(tr+hs,tc+hs,dr,dc,hs,b);
		}
	} 
}
int main()
{
	//左下残缺 右下残缺 左上残缺 右上残缺
	//1 1      2 2        3      4
	//  1      2        3 3      4 4
	//把基础的四格情况分为四种样式的图形，去图形式的填充
	
	int k;
	printf("输入棋盘2^k×2^k的k值：");
	scanf("%d",&k);
	int size = mpow(2,k);
	//printf("size = %d\n",size);
	
	int *b[size]; //生成棋盘矩阵
	for(int i = 0;i < size;i++)
	{
		b[i] = (int*)malloc(sizeof(int)*size);
	}
	for(int i = 0;i < size;i++)
	{
		for(int j = 0;j < size;j++)
		{
			b[i][j] = -1;
		}
		//puts("");
	}
	
	printf("输入残缺位置（行 列）：");
	scanf("%d %d",&qa,&qb);
	int dr,dc;
	dr = qa;
	dc = qb;
	
	if((qa < size && qa >= 0) && (qb < size && qb >= 0))
	{
		b[qa][qb] = 0;
		generateBoard(0,0,dr,dc,size,b);
		
		for(int i = 0;i < size;i++)
		{
			for(int j = 0;j < size;j++)
			{
				printf("%d  ",b[i][j]); 
			}
			puts("");
		}
	}
	else
	{
		printf("残缺位置不在棋盘上，位置不合法！");
	}
	for(int i = 0;i < size;i++)
	{
		free(b[i]);
	}
	system("pause");
	return 0;
}

MyCoverBoardA.c-运行结果示例

1.k为1

   1.1缺陷在1 0位置

在这里插入图片描述

   1.2缺陷在0 0位置

在这里插入图片描述

2.k为2

   2.1缺陷在1 2位置

在这里插入图片描述

   2.2缺陷在2 3位置

在这里插入图片描述

3.k为3

   3.1缺陷在5 6位置

在这里插入图片描述

   3.1缺陷在4 2位置

在这里插入图片描述

4.k为4

4.1   3.1缺陷在12 9位置

在这里插入图片描述

MyCoverBoardB.c-运行结果示例

1.k为1

   1.2缺陷在0 0位置

在这里插入图片描述

   1.1缺陷在0 1位置

在这里插入图片描述

   1.1缺陷在1 0位置

在这里插入图片描述

   1.2缺陷在1 1位置

在这里插入图片描述

2.k为2

   2.1缺陷在1 2位置

在这里插入图片描述

   2.2缺陷在2 3位置

在这里插入图片描述

3.k为3

   3.1缺陷在5 6位置

在这里插入图片描述

   3.1缺陷在4 2位置

在这里插入图片描述

4.k为4

4.1   3.1缺陷在12 9位置

在这里插入图片描述

------------------------------------------------------第十次发项目类文章有点激动啊！-----------------------------------------------------
-----------------------------------------------------【C语言—微项目—自编练习】----------------------------------------------------------
----------------------------------------------------------------【TDTX】--------------------------------------------------------------------------

C语言【微项目】C语言棋盘问题棋盘覆盖图形式覆盖排他式覆盖分治法算法

相关

C语言%d%c%f

数据结构--栈（C语言实现）

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

C语言内存管理--作用域和生命周期

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

算法第四章实践报告

关于tarjan算法的一些整理

【基础】排序算法学习笔记

标签