棋盘覆盖问题（分治法）

超、凢脫俗 2023-05-22 22:15 40阅读 0赞

## 问题描述 ##

**有一个2k×2k（k>0）的棋盘，恰好有一个方格与其他方格不同，称之为特殊方格，并且称该棋盘为一特殊棋盘。现在要用4种不同形状的三格骨牌覆盖除了特殊方格外的其他全部方格，并且任何两个三格骨牌不能重叠。请给出一种覆盖方案**

##### 特殊棋盘（k=3时） #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]

##### 四种形状的三格骨牌 #####

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

## 求解过程 ##

①使用二分法对整个棋盘进行划分（分为四个象限）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]  
②对特殊方格所不在的象限中心进行填充  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]  
③对每个象限再次使用二分法进行划分（分为四个象限）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]  
④对特殊方格所不在的象限中心进行填充  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 4]  
⑤继续对每个小象限进行划分  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 5]  
⑥再次进行填充，即完成

## 实现代码 ##

##### 初始化棋盘 #####

//棋盘
    private int board[][];
    //不同类型的三格骨牌
    private int type;
    
    /**
      * 初始化棋盘
      * @param x 棋盘行数
      * @param y 棋盘列数
      * @param m 棋盘特殊点横坐标
      * @param n 棋盘特殊点纵坐标
      */
     public ChessCover(int x,int y, int m, int n) {
      	this.board = new int[x][y];
      	//特殊点赋为-1
      	this.board[m][n] = -1;
      	this.type = 1;  
      	//构造棋盘
      	cheCover(0, 0, m, n, board.length);
     }

##### 构造棋盘 #####

\*\*该算法中需要注意的是临界值的考虑，即 <、>、<=、>=的使用

/**
      * 使用二分法铺满棋盘
      * @param x 开始横坐标（棋盘顶角）
      * @param y 开始纵坐标（棋盘顶角）
      * @param dx 特殊点横坐标
      * @param dy 特殊点纵坐标
      * @param size 划分后的棋盘大小
      */
     private void cheCover(int x, int y, int dx, int dy, int size){
      	//递归出口
      	if(size == 1) {
       		return;
      	}
      	
      	//不同类型的三格骨牌
      	int i = this.type++;
      	//将棋盘分割为四个象限
      	size = size/2;
      	
      	//处理左上角
      	if(dx < x+size && dy < y+size) {
       		//特殊点若在左上角
       		cheCover(x, y, dx, dy, size);
      	}else {
       		//特殊点若不在左上角，对该象限右下角进行填充
       		this.board[x+size-1][y+size-1] = i;
       		cheCover(x, y, x+size-1, y+size-1, size);
      	}
      	
      	//处理右上角
      	if(dx < x+size && dy >= y+size) {
       		//特殊点若在右上角
       		cheCover(x, y+size, dx, dy, size);
      	}else {
       		//特殊点若不在右上角，对该象限左下角进行填充
      		this.board[x+size-1][y+size] = i;
       		cheCover(x, y+size, x+size-1, y+size, size);
      	}
      	
      	//处理左下角
      	if(dx >= x+size && dy < y+size) {
       		//特殊点若在左下角
       		cheCover(x+size, y, dx, dy, size);
      	}else {
       		//特殊点若不在左下角，对该象限右下角进行填充
       		this.board[x+size][y+size-1] = i;
       		cheCover(x+size, y, x+size, y+size-1, size);
      	}
      	
      	//处理右下角
      	if(dx >= x+size && dy >= y+size) {
       		//特殊点若在右下角
       		cheCover(x+size, y+size, dx, dy, size);
      	}else {
       		//特殊点若不在右下角，对该象限左下角进行填充
       		this.board[x+size][y+size] = i;
      		cheCover(x+size, y+size, x+size, y+size, size);
      	}
     }

## 测试结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 6]  
示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 7]

## 时间及空间复杂度 ##

##### 时间 #####

递归方程：  
T(1）= O(1)                   k=0  
T(k) = 4T(k-1) + O(1)     k>0

即，平均时间复杂度为T(k) = O(4k)  
由于在覆盖2k\*2k大小的棋盘时使用了(4k\-1)/3个三格骨牌，与时间分治法求得的时间复杂度同阶，即该算法是渐进最优算法

##### 空间 #####

S(n) = O(1)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]: /images/20230521/31b5ffe3f2b44d72b8f86e8357c1ef4a.png
[20200418151655823.png]: /images/20230521/f19cb126bfcc4ec99089698d193511ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]: /images/20230521/cab9d2bc83a0406f88ab096eb2f2df96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]: /images/20230521/3e0ea94c5dbd4bd295b650920a2aef79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]: /images/20230521/d810c59148c94958a1dd427296c92c38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 4]: /images/20230521/e74a514b72144587a30c75ccd217b36a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 5]: /images/20230521/4dcdd1c6aacf491bb37bbd6d7192032b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 6]: /images/20230521/d4bd78c2b0f8477f9ba5e008686d506e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 7]: /images/20230521/01078831ec2c492dbe3eb9afe272a916.png