分治算法-棋盘覆盖问题

我不是女神ヾ 2024-04-23 20:02 84阅读 0赞

在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

![image.png][]  
![image.png][image.png 1]  
![image.png][image.png 2]  
![image.png][image.png 3]

#include<stdio.h>
    #define MAX 1025
    
    //问题表示
    int k;				//棋盘大小
    int x,y;			//特殊方格的位置
    
    //求解问题表示
    int board[MAX][MAX];
    int tile=1;		
    
    void ChessBoard(int tr,int tc,int dr,int dc,int size)
    {
           if(size==1) return;		//递归出口
        int t = tile++;			//取一个L型骨，其牌号为tile
        int s = size/2;			//分割棋盘
     
        //考虑左上角象限
        if(dr<tr+s && dc<tc+s) {
         //特殊方格在此象限中
    		ChessBoard(tr,tc,dr,dc,s);
        } else {
         //此象限中无特殊方格
            board[tr+s-1][tc+s-1]=t;	//用t号L型骨牌覆盖右下角
    		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]=t;	//用t号L型骨牌覆盖左下角
    		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]=t;  //用t号L型骨牌覆盖右上角
            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]=t;  //用t号L型骨牌覆盖左上角
    		ChessBoard(tr+s,tc+s,tr+s,tc+s,s);  //将左上角作为特殊方格继续处理该象限
        }
    }

![image.png][image.png 4]

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/a52c38566e474a7eacbe473c12fab16e.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c87f0bde6d5840148fc26b02fca7e28d.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/bc8bb4856d7e42a4904051c12ef32045.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/efa58f03999f48719ef0db0ef7811b3f.png
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c29de70e006d4c239d360eae2321d377.png