算法设计与分析——递归与分治策略——棋盘覆盖

小灰灰 2022-11-07 14:51 390阅读 0赞

**问题描述**  
棋盘覆盖问题要求在2^k \* 2^k 个方格组成的棋盘中，你给定任意一个特殊点，用一种方案实现对除该特殊点的棋盘实现全覆盖。

建立模型如图：

解决方案就是利用分治法，将方形棋盘分成4部分，如果该特殊点在某一部分，我们就去递归他，如果不在某一部分，我们假设一个点为特殊点，同样递归下去，知道全覆盖。

左上角的子棋盘（若不存在特殊方格）：则将该子棋盘右下角的那个方格假设为特殊方格；

右上角的子棋盘（若不存在特殊方格）：则将该子棋盘左下角的那个方格假设为特殊方格；

左下角的子棋盘（若不存在特殊方格）：则将该子棋盘右上角的那个方格假设为特殊方格；

右下角的子棋盘（若不存在特殊方格）：则将该子棋盘左上角的那个方格假设为特殊方格；

在一个2^k \* 2^k个方格组成的棋盘中，有一个方格与其它的不同，若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格，如何覆盖。四个L型骨牌如下图：  
![在这里插入图片描述][20210602194608181.png]

![在这里插入图片描述][20210602194616412.png]

实现的基本原理是将2^k \* 2k的棋盘分成四块2(k - 1) \* 2^(k - 1)的子棋盘，特殊方格一定在其中的一个子棋盘中，如果特殊方格在某一个子棋盘中，继续递归处理这个子棋盘，直到这个子棋盘中只有一个方格为止如果特殊方格不在某一个子棋盘中，将这个子棋盘中的相应的位置设为骨牌号，将这个无特殊方格的了棋盘转换为有特殊方格的子棋盘，然后再递归处理这个子棋盘。以上原理如图所示：

![在这里插入图片描述][20210602194535193.png]

#include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    int tile = 1;
    int Borad[100][100];
    /**
     * tr : 棋盘左上角的行号，tc棋盘左上角的列号
     * dr : 特殊方格左上角的行号，dc特殊方格左上角的列号
     * size ：size = 2^k 棋盘规格为2^k*2^k
     */
    void ChessBoard(int tr,int tc,int dr,int dc,int size)
    {
        
        if(size==1)
            return;
        int t = tile++;
        int s = size / 2;
        if( dr< tr+s && dc< tc+s )//特殊方格在棋盘的左上角
        {
        
            ChessBoard(tr, tc, dr, dc, s);
        }
        else//特殊方格不在棋盘的左上角时；
        {
        
            Borad[tr + s-1][tc + s-1] = t;
            ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
    
        }
    
        if( dr< tr+s && tc+s <=dc )//特殊方格在棋盘的右上角
        {
        
            ChessBoard(tr, tc + s, dr, dc, s);
        }
        else//特殊方格不在棋盘的右上角
        {
        
            Borad[tr + s-1][tc + s]=t;
            ChessBoard(tr, tc + s, tr + s-1, tc + s , s);
        }
        
        if( tr+s<= dr && dc < tc+s )//特殊方格在棋盘的左下角
        {
        
            ChessBoard(tr + s, tc, dr, dc, s);
        }
        else//特殊方格不在棋盘的左下角
        {
        
            Borad[tr+s][tc+s-1]=t;
            ChessBoard(tr + s, tc, tr+s, tc+s-1, s);
        }
    
        if( tr+s <= dr && tc+s <= dc )//特殊方格在棋盘的右下角
        {
        
            ChessBoard(tr + s, tc + s, dr, dc, s);
        }
        else//特殊方格不在棋盘的右下角
        {
        
            Borad[tr + s][tc + s]=t;
            ChessBoard(tr + s, tc + s, tr+s, tc+s, s);
        }
    
    
    
    
    
    
    }
    int main()
    {
        
        cout << "输入K的值：";
        int k;
        cin >> k;
        int temp = 1;
        for (int i = 0; i < k;i++)
        {
        
            temp = temp * 2;
        }
        int size = temp;
        int x, y;//存储特殊点所在的行列
        cout << "输入特殊点在的行,列：(表示特殊点的值为-1)：";
        cin >> x >> y;
        Borad[x][y] = -1;
        ChessBoard(0, 0, x, y, size);
        for (int i = 0; i < size;i++)
        {
        
            for (int j = 0; j < size;j++)
            {
        
                cout <<setw(4)<< Borad[i][j]<<" ";
            }
            cout << endl;
        }
            system("pause");
    
    }

上述算法中：  
使用了一个二维数组Board\[\]\[\]表示棋盘，Board\[0\]\[0\]是棋盘左上角的方格，tile是算法中的一个全局变量，用来表示L型骨牌，其初始值为0。  
tr:棋盘左上角方格的行号  
tc:棋盘左上角方格的列号  
dr:特殊方格的行号  
dc:特殊方格的列号  
size:size=2^k，  
棋盘的规格=2^K\* 2^K  
![在这里插入图片描述][20210314124918738.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]

标记的次序：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]

[20210602194608181.png]: /images/20221023/78f37c5b6c1146f3a1d163cf0613a5db.png
[20210602194616412.png]: /images/20221023/2017ccc20db84149aefa77ad6fcb4640.png
[20210602194535193.png]: /images/20221023/15a795df45e84dffb26fb688e7109750.png
[20210314124918738.png]: /images/20221023/05428260be084d28aec339491951d11c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221023/f889632e4f664c9284f0df226374ed37.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]: /images/20221023/58bdf1b6348746379bf7287af86d2a0a.png