棋盘覆盖问题

曾经终败给现在 2023-06-11 08:23 6阅读 0赞

# 棋盘覆盖问题 #

在一个2k✖2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格，并且这个棋盘就称为特殊棋盘。显然，这个特殊方格在棋盘中出现的位置由4k中情形； 例如当 k = 2 时，特殊方格可以是16个方格中的任意一格；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXl1YW4xNTk_size_16_color_FFFFFF_t_70]

如上图（1）所示，数组【0】【1】的位置就是特殊方格的位置，这个特殊方格可 以在16个方格中的任意位置。  
然后，要用如下图（2）四种不同形态的L型骨牌覆盖掉除特殊方格中的所有方格，条件是不得重叠，即一个格子中不得覆盖两次及以上的L型骨牌。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXl1YW4xNTk_size_16_color_FFFFFF_t_70 1]  
将上图中所示的四种型号的骨牌对图一进行覆盖填充，除特殊棋盘为刚好能覆盖掉整个棋盘，结果如下所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXl1YW4xNTk_size_16_color_FFFFFF_t_70 2]  
下面进行棋盘的覆盖（途中特殊方格表示0，数字下标位置为【0】【1】），所用到的方法是：

1.  先将图中所示棋盘分割为4小格，即将size为4×4的格子分成4个2×2的格子（当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1子棋盘）。
2.  我们分别叫它左上、右上、左下、右下棋盘，如果特殊棋盘在左上（子棋盘中），我们将没有特殊方格所在的其他三个子棋盘进行覆盖，如上图标1的地方，（当然这不是第一步就把1标注在图所在位置上，因为棋盘覆盖使用了递归的方法，这里只是为了便于理解）。
3.  继续进行棋盘分割，直至棋盘分割到最小单元（1×1的子棋盘）

**用编程语言进行实现，主要时利用了二维数组，首先定义棋盘的大小，之后输入特殊方格所在的位置（数组下标），然后在二维数组中进行相同数字(一组相同数组表示4种L型骨牌中的一个)的填充（即覆盖）**

c++代码的实现

#include <iostream>
    #include <cstring>
    #include <cstdio>
     
    using namespace std;
    //tr表示棋盘左上角行号
    //tc表示棋盘左上角列号
    //dr表示特殊棋盘的行号
    //dc表示特殊棋盘的列号
    //size = 2^k
    //棋盘的规格为2^k * 2^k
    const int SIZE = 8;
    static int tt = 1;
    static int board[SIZE][SIZE];
    void ChessBoard(int tr,int tc,int dr,int dc,int size)
    {
        
        if(size == 1)//棋盘只有一个方格且是特殊方格
            return ;
        int t = tt++; //L型骨牌号
        int s = size>>1;//分割棋盘
         //覆盖左上角子棋盘
        if(dr<tr+s&&dc<tc+s)
            ChessBoard(tr,tc,dr,dc,s); //特殊方格在此棋盘中
        else
        {
        
             //此棋盘无特殊方格
             //用t号L型骨牌覆盖右下角
            board[tr+s-1][tc+s-1] = t;
            //覆盖其余方格
            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
        {
        
             //此子棋盘中无特殊方格
             //用t号L型骨牌覆盖左下角
            board[tr+s-1][tc+s] = t;
             //覆盖其余方格
            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
         {
        
             //用t号L型骨牌覆盖右上角
             board[tr + s][tc + s -1] = t;
             //覆盖其余方格
             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
         {
        
             //用t号L型骨牌覆盖左上角
             board[tr + s][tc + s] = t;
             //覆盖其余方格
             ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
         }
    }
    void ChessPrint()
    {
        
        for(int i = 0; i < SIZE; i++)
        {
        
            for(int j = 0; j < SIZE; j++)
            {
        
                cout.width(3);
                cout<<board[i][j]<<" ";
            }
           cout<<endl;
        }
    }
    int main()
    {
        
        int x,y;
        cin>>x>>y;
        ChessBoard(0,0,x,y,SIZE);
        ChessPrint();
    	system("pause");
        return 0;
    }

以上代码是一个定义了棋盘大小为8的特殊棋盘。其结果如下，我们输入2、2（将特殊方格定位的数字下标为【2】【2】的位置）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXl1YW4xNTk_size_16_color_FFFFFF_t_70 3]  
其递归的过程如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXl1YW4xNTk_size_16_color_FFFFFF_t_70 4]

以下是java语言的实现：

package recursion;
    
    public class chessBoard {
        
        static int size=8;
        static int tt = 1;
        static int board[][] = new int[size][size];
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
           int x,y;
           x=2;
           y=2;
           chessBoard(0,0,x,y,size);
           Chessprint();
           
    	}
    	
    	public static  void chessBoard(int tr,int tc,int dr,int dc,int size){
        
    		//tr和tc是棋盘左上角的下标，dr和dc是特殊方格的下标
    		//size是棋盘的大小，t已经初始化为0；
    		if(size == 1) return ;
    		int t = tt++; //L型骨牌号
    		int s = size/2;//分割棋盘
    		
    		//覆盖左上角子棋盘
    		if(dr<tr+s && dc<tc+s)
    			//特殊方格在此棋盘中
    		  chessBoard(tr,tc,dr,dc,s);
    		else{
        //此棋盘中无特殊方格
    			//用t号L型骨牌覆盖右下角
    			board[tr+s-1][tc+s-1]=t;
                //覆盖其余方格
    			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{
        //此棋盘中无特殊方格，
    			//用t号L型骨牌覆盖左下角
    			board[tr+s-1][tc+s] = t;
    			//覆盖其余方格
    			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{
         //用t号L型骨牌覆盖右上角
    			board[tr+s][tc+s-1] =t;
    			//覆盖其余方格
    			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{
        
    			//用t号L型骨牌覆盖左上角
    			board[tr+s][tc+s]=t;
    			//覆盖其余方格
    			chessBoard(tr+s,tc+s,tr+s,tc+s,s);
    		}
    	}  
      
    	public static void Chessprint(){
        
    		for(int i=0;i<size;i++){
        
    			for(int j=0;j<size;j++){
        
    				System.out.print(board[i][j]+"  ");
    			}
    			System.out.println();
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXl1YW4xNTk_size_16_color_FFFFFF_t_70]: /images/20230531/5d29dfbeb7ae4578929463aa09c911c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXl1YW4xNTk_size_16_color_FFFFFF_t_70 1]: /images/20230531/0f6b3b7ffa0a4e4b8a3f85e95516818f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXl1YW4xNTk_size_16_color_FFFFFF_t_70 2]: /images/20230531/85a5cd1e45644f69b32e14ea8834cc34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXl1YW4xNTk_size_16_color_FFFFFF_t_70 3]: /images/20230531/eebbdd8fbb7c4d01aecd67e5a4ee71e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXl1YW4xNTk_size_16_color_FFFFFF_t_70 4]: /images/20230531/2b9121bba801419da732f0b13f8728f5.png