递归与分治策略算法之棋盘覆盖问题

迈不过友情╰ 2022-12-05 04:58 166阅读 0赞

## 递归与分治策略算法之棋盘覆盖问题 ##

**1、先简单的来介绍一下分治策略的思想**

分治策略的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，分解出来的子问题与原问题相同，并且相互独立。通过递归去解决子问题，然后将子问题的解合并得到原问题的解。

--------------------

**2、棋盘覆盖问题的介绍**

在一个 2 k 2^k 2k\* 2 k 2^k 2k方格组成的棋盘中，**恰有一个方格**与其他方格不同，称该方格为特殊方格，称该棋盘为特殊棋盘。  
现在要让这个大的特殊棋盘中的每个小的子棋盘都变成特殊棋盘，即子棋盘中都有一个特殊方格。这里就需要用到L型骨牌去覆盖，规定任何两个L型骨牌不得重叠。在一个 2 k 2^k 2k\* 2 k 2^k 2k方格组成的棋盘中，用到的L型骨牌个数恰好为(4^(k-1)) / 3。

如图，给出一个4\*4的棋盘，特殊方格用蓝色方格标出，给出四种骨牌形式用于放在子棋盘的会合处。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]  
以上图4\*4的特殊棋盘为例，用L型骨牌将其划分为特殊的子棋盘，如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 1]  
这样就简单的完成了一个对4\*4的棋盘的覆盖问题。

--------------------

**3、棋牌覆盖问题的具体实现**

采用分治策略的思想，将棋盘的规模每次缩小一半（例如：给出8\*8的棋盘，规模缩小一半为4\*4的子棋盘）。此时，特殊方格必然位于4个子棋盘之中，然后通过如下步骤利用L型骨牌将其子棋盘划分为特殊子棋盘。

*  若左上角子棋盘中存在特殊方格，则直接划分；若不存在，则将左上角子棋盘的右下角方格变成一个特殊方格；
 *  若右上角子棋盘中存在特殊方格，则直接划分；若不存在，则将右上角子棋盘的左下角方格变成一个特殊方格；
 *  若左下角子棋盘中存在特殊方格，则直接划分；若不存在，则将左下角子棋盘的右上角方格变成一个特殊方格；
 *  若右下角子棋盘中存在特殊方格，则直接划分；若不存在，则将右下角子棋盘的左上角方格变成一个特殊方格；
 *  直到棋盘规格变成2\*2结束；

通过上述步骤，可以动态确定L型骨牌的类型，即其余三个非特殊子棋盘变成特殊子棋盘时，在会合处改变的那个特殊方格连接起来就为一个L型骨牌；

具体实现：

以8\*8的棋盘为例，进行棋盘覆盖问题

#include <stdio.h>
    #include <stdlib.h>
    
    #define N 8
    //将棋盘采用分治策略，划分为小问题
    int Board[N][N];//定义N*N的棋盘,值为0，表示特殊方格，值为1，表示普通方格
    
    
    //划分棋盘，参数是棋盘，tr,tc是棋盘左上角的行列号，dr,dc是特殊方格的行列号，size是棋盘的规格
    void ChessBoard(int tr, int tc, int dr, int dc, int size)
    {
        
    	if (size == 2)//边界,2*2棋盘
    		return;
    
    	//开始划分成小问题
    	int s = size / 2;//规格缩小
    
    	//搜索子棋盘
    	if (dr < tr + s && dc < tc + s)
    	{
        
    		//特殊方格在左这左上子棋盘中,直接将其划分子棋盘
    		ChessBoard(tr, tc, dr, dc, s);
    	}
    	else
    	{
        
    		//左上子棋盘无特殊方格,用L型骨牌覆盖右下角
    		Board[tr + s - 1][tc + s - 1] = 0;
    		//继续划分子棋盘
    		ChessBoard(tr, tc, tr + s - 1, tc + s - 1,s);
    	}
    
    	if (dr < tr + s && dc >= tc + s)
    	{
        
    		//特殊方格在右上子棋盘中,直接将其划分子棋盘
    		ChessBoard(tr, tc + s, dr, dc, s);
    	}
    	else
    	{
        
    		//右上子棋盘无特殊方格,用L型骨牌覆盖左下角
    		Board[tr + s - 1][tc + s] = 0;
    		//继续划分子棋盘
    		ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
    	}
    
    	if (dr >= tr + s && dc < tc + s)
    	{
        
    		//特殊方格在左下子棋盘中,直接将其划分子棋盘
    		ChessBoard(tr + s, tc, dr, dc, s);
    	}
    	else
    	{
        
    		//左下子棋盘无特殊方格,用L型骨牌覆盖右上角
    		Board[tr + s][tc + s - 1] = 0;
    		//继续划分子棋盘
    		ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
    	}
    
    	if (dr >= tr + s && dc >= tc + s)
    	{
        
    		//特殊方格在右下子棋盘中,直接将其划分子棋盘
    		ChessBoard(tr + s, tc + s, dr, dc, s);
    	}
    	else
    	{
        
    		//右下子棋盘无特殊方格,用L型骨牌覆盖左上角
    		Board[tr + s][tc + s] = 0;
    		//继续划分子棋盘
    		ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
    	}
    
    }
    
    
    int main()
    {
        
    	
    	//棋盘初始化
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < N; j++)
    			Board[i][j] = 1;
    
    	//假设初始时，特殊方格在Board[0][2]位置
    	Board[0][2] = 0;
    
    	//划分棋盘
    	ChessBoard(0, 0, 0, 2, N);
    
    	//打印划分完成后的棋盘
    	for (int i = 0; i < N; i++)
    	{
        
    		for (int j = 0; j < N; j++)
    			printf("%d  ", Board[i][j]);
    		printf("\n");
    	}
    		
    	return 0;
    }

实现结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 2]

--------------------

tips：没有激流就称不上勇进，没有山峰则谈不上攀登。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/9594f6709d7840f8b6f8a51cc7c26971.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/067bc9fd0e5241e483cff0afc7dd17ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/2f60fd7a788c4cb3a771402bf4970b7f.png