算法分析之棋盘覆盖问题

青旅半醒 2022-12-08 05:46 176阅读 0赞

## 算法分析之棋盘覆盖问题 ##

**一，问题描述**

在一个2k×2k个方格组成的棋盘中，有一个方格与其它的不同，使用四种L型骨牌覆盖除这个特殊方格的其它方格，请使用分治法实现棋盘覆盖

**<1>分析：**  
四个L型骨牌如下图：  
![在这里插入图片描述][20200918185439456.png_pic_center]

棋盘覆盖问题是指，要用图2中的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。用分治法设计一个求解棋盘覆盖问题的算法，并且用c++语言实现。

首先明确 要使用分制的思想。  
(1) 把棋盘等分成四个正方形分别是：左上、左下、右上、右下 四个子棋盘。  
(2) 对于每一个子棋盘，如果其存在特殊方格，将它再分成四个子棋盘，并且使用同样的方法，对子棋盘进行递归。  
(3)对于不存在特殊方格的子棋盘，假定与另外三个子棋盘相接的为特殊方格，有了特殊方格之后，对这个子棋盘进行递归  
(4)直到子棋盘为1\*1的正方形。

**代码实现**

```c
    #include <iostream>
    #include <stdio.h>
    using namespace std;
    int def[300][300]={
        0};
    static int t=0;
    void chess(int a,int b,int ta,int tb,int length){
        
    //a,b为子棋盘左上角坐标，ta,tb为特殊点坐标，length为子棋盘长度
    if(length==1){
        
    //如果length等于1，说明是1*1的棋盘，就存在一个位置，即特殊方格的位置
            return;
        }
        t++; 
        int tem =t;
        int p=length/2;                     //分割棋盘
    
        if(ta<a+p && tb<b+p){
                  //特殊点在左上的正方形中
            chess(a,b,ta,tb,p);
        }
        else{
                                  //此棋盘中没有特殊方格
            def[a+p-1][b+p-1]=tem;
            chess(a,b,a+p-1,b+p-1,p); 	//覆盖棋盘其余区域
        }
    
        if(ta>=a+p && tb<b+p){
                  //左下角的子棋盘
            chess(a+p,b,ta,tb,p);
        }
        else{
        
            def[a+p][b+p-1]=tem;
            chess(a+p,b,a+p,b+p,p);
        }
     
        if(ta<a+p && tb>=b+p){
                  //右上角的子棋盘
            chess(a,b+p,ta,tb,p);
        }
        else{
        
            def[a+p-1][b+p]=tem;
                  chess(a,b+p,a+p-1,b+p,p);
        }
        if(ta>=a+p && t>=b+p){
        
            chess(a+p,b+p,ta,tb,p);
        }
        else{
        
            def[a+p][b+p]=tem;
                    chess(a+p,b+p,a+p,b+p,p);
        }
    }
    int main(){
        
        int n,a,b,ta,tb,length,m;
        //a,b是子棋盘左上角的行号和列号
        //ta,tb是特殊点的行号和列号
        cout<<"请输入请输入比例为2^n的棋盘大小:";
        cin>>length;
        cout<<"请输入特殊点行号:";
        cin>>ta;
        cout<<"请输入特殊点列号:";
        cin>>tb;
        a=b=1;
        m=length;
        chess(a,b,ta,tb,length);
        for(int i=1;i<=m;i++){
                 //遍历棋盘，输出结果
            for(int j=1;j<=m;j++){
        
                cout.width(3);
                cout<<def[i][j];
                if(j==m){
        
                    cout<<endl;
                }
            }
        }
    }

**结果分析：**

分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题，就可以得到每一步的运行结果。这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解。

[20200918185439456.png_pic_center]: /images/20221123/d8e9f765d2b244f9a2078d130ff5925b.png