棋盘覆盖问题题解

一时失言乱红尘 2022-12-28 14:15 337阅读 0赞

### 文章目录 ###

*  问题
 *  代码

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

# 问题 #

在一个2k × 2k个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘。现用若干个L型骨牌覆盖在一个给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖

我们先来看一个k = 2时的棋盘覆盖问题

![1][]

而骨牌的形状如下

![2][]

对于k = 2的特殊棋盘，使用的骨牌数为 (22 × 22 \-1) /3 = 5个

>  *  同理递推到k = n 的特殊棋盘中，使用的骨牌数为\*\*(2n × 2n \- 1)/3 个\*\*

那我们怎么去解决这个问题呢？

如果采用分治的思想去看这个问题的话，就应该是去将一个2k × 2k 的特殊棋盘分解成子问题，而这个子问题应该就是将棋盘等分成4个2k-1 × 2k-1相同规模的棋盘。

**但是这里就出现了问题，可以很明显的发现，我们划分出来的子问题和原问题不是同相同的问题。子问题中特殊方格一定存在于4个子棋盘中的任意1个，但是其他3个棋盘中不存在特殊方格，也就不再是特殊棋盘，因此这两个子问题是不同的**

**如何解决这个问题？**

我们可以通过一个L型的骨牌来使得4个相同规模的子问题相同，即将其他的3个棋盘也加上特殊方格

![3][]

因此这个问题就变得容易解决了，在每次将问题分解成子问题时，就在其他3个方格的中心角处加上特殊方格，直到k = 1时，即2 × 2的棋盘

# 代码 #

以该棋盘为例

![1][]

最终输出

2   2   3   3   
    2   1   1   3   
    4   1   0   5   
    4   4   5   5

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    #define BOARD_SIZE 4
    int board[BOARD_SIZE][BOARD_SIZE];
    
    // tc, tr: 棋盘左上角的行号和列号
    // dc, dr: 特殊方格的行号和列号
    // size = 2 ^ k
    int tile = 1;    //tile为当前骨牌的号数
    void chessboard(int tr, int tc, int dr, int dc, int size)
    {
        
        if(size == 1) return;
        int s;
        int d = tile++; //d为L型骨牌号
        s = size / 2;
       
        //特殊方格在左上角子棋盘
        if(dr < tr + s && dc < tc + s)
        {
        
           chessboard(tr, tc, dr, dc, s);
        }
        else   // 不在此棋盘，将此棋盘右下角设为相应的骨牌号
        {
        
           board[tr + s - 1][tc + s - 1] = d;
           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  // 不在此棋盘，将此棋盘左下角设为相应的骨牌号
        {
        
           board[tr + s - 1][tc + s] = d;
           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  // 不在此棋盘，将此棋盘右上角设为相应的骨牌号
        {
        
           board[tr + s][tc + s - 1] = d;
           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   // 不在此棋盘，将此棋盘左上角设为相应的骨牌号
        {
        
           board[tr + s][tc + s] = d;
           chessboard(tr + s, tc + s, tr + s, tc + s, s);
        }
    }
    
    int main()
    {
        
        int i, j;
        board[2][2] = 0;
        chessboard(0, 0, 2, 2, BOARD_SIZE);
        for(i = 0; i < BOARD_SIZE; i++)
        {
        
            for(j = 0; j < BOARD_SIZE; j++)
            {
        
               printf("%-4d", board[i][j]);
            }
            printf("\n");
        }
    }

[1]: /images/20221120/bedb16b6becb45368b3336745e3d5a91.png
[2]: /images/20221120/1ff1a22103644e1fabe8aee36a86281e.png
[3]: /images/20221120/3ffb8e871a9f4522b97b75a5e6612077.png