【分治法】棋盘覆盖问题java实现

「爱情、让人受尽委屈。」 2023-03-13 13:18 26阅读 0赞

### 文章目录 ###

*   *   *  问题描述
         *  问题分析
         *  算法设计
         *  java代码

### 问题描述 ###

在一个2k × 2k个放个中，恰好只有一个方格是残缺的。也就是在这个棋盘中有一个方格与其它的格子不同， 我们称这种棋盘为残缺棋盘。

下图所示k=2时，也就是一个22 × 22的棋盘，其中第一行第二列这个方格为一个与众不同的方格。  
![在这里插入图片描述][2020051408525183.png]  
覆盖是指，用L型骨牌覆盖残缺棋盘上所有方格，覆盖是要求二任何两个L型骨牌不能重叠。

### 问题分析 ###

首先分析一下用于覆盖的骨牌的情况，那么L型骨牌有几种了？  
观察发现，L型骨牌是可以旋转的。经过旋转后有四种情况，如下图所示，  
![在这里插入图片描述][20200514085752714.png]  
残缺方格共有2k × 2k种，对于任何k>=0,残缺棋盘有2k × 2k种。

2k × 2k的棋盘中有一个是残缺方格，因此有4k个方格，除去一个残缺的方格，共有4k \- 1个方格要覆盖，而每个骨牌有三个格子，因此，用到的骨牌数量应该是（4k \-1)/3个。

下图给出了一个覆盖的实例。在这个棋盘中，共有15空格要覆盖，15/3=5。5个L型骨牌进行覆盖。  
![在这里插入图片描述][2020051409054641.png]

### 算法设计 ###

采用分治的策略，第一个关键问题为分割，将原问题分割为若干个小规模的问题。那么怎么分割呢？  
当k>0时，将2k × 2k棋盘分割为4个2k \-1× 2k\-1的子棋盘。  
问题规模由原来的2k 变为2k-1 。子问题的规模是原问题的一半。

那么对应的四个子问题分别是什么情况呢？  
此时，残缺方格一定位于四个子棋盘之一，因为残缺方格只有一个。问题规模由原来的2k 变为2k-1 ，子问题的规模是原问题规模的一半。

对于2k × 2k的棋盘有如下的特点：  
1、正方形  
是否能将问题分治为多个子问题。  
2、棋盘上有一个残缺方格  
分解后的子问题汇中应该有一个残缺方格

**通过观察我们可以发现，分解后的子问题中，有三个棋盘没有残缺，与原问题不同。而分治法要求，子问题相互独立且与原问题相同**，因此将剩余三个棋盘转换为残缺棋盘用L型骨牌覆盖这三个较小棋盘的结合处。  
L型骨牌恰好有三个方格，我们用这三个方格覆盖3个子棋盘的结合处。这三个棋盘上被L型骨牌覆盖的方格，就成为该棋盘上的残缺方格。这样就将原问题分解为4个较小规模的棋盘覆盖问题。  
![在这里插入图片描述][20200514100420614.png]  
对于子问题怎么求解了？  
每一次分割都可以将原问题的规模缩小二分之一，针对这类问题，可以递归的使用这种分割方法吗，知道把问题化简到一个可解的状态。

### java代码 ###

package com.java2;
    
    public class ChessBoard
    {
        
    	int tile=1;//表示L型骨牌的编号
    	int[][] board = new int[4][4];//表示棋盘
    	//处理带有特殊棋子的棋盘.tr、tc表示棋盘的入口即左上角的行列号，dr、dc表示特殊棋子的行列位置，size表示棋盘的行数或者列数
    	public void chessBoard(int tr, int tc, int dr, int dc, int size)
    	{
        
    		if(size == 1) return;
    		int t = tile++;
    		System.out.println(t);
    		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型的骨牌覆盖。由于骨牌有三种，当处理过程中同一级设置的特殊棋子用相同的骨牌覆盖
    			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型的骨牌覆盖。由于骨牌有三种，当处理过程中同一级设置的特殊棋子用相同的骨牌覆盖
    			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型的骨牌覆盖。由于骨牌有三种，当处理过程中同一级设置的特殊棋子用相同的骨牌覆盖
    			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型的骨牌覆盖。由于骨牌有三种，当处理过程中同一级设置的特殊棋子用相同的骨牌覆盖
    			chessBoard(tr+s,tc+s,tr+s,tc+s,s);//处理有用 骨牌覆盖的格子作为特殊棋子的右下角子棋盘
    		}
    	}
    	
    	public static void main(String[] args)
    	{
        
    		ChessBoard c = new ChessBoard();
    		c.chessBoard(0,0,1,1,4);
    		for(int i = 0; i <4; i++)
    		{
        	for(int j = 0; j <4; j++)
    			    System.out.print(c.board[i][j]+"  ");
    		System.out.println();
    		}
    	}
     
    }

[2020051408525183.png]: /images/20230312/11bd4a46bf9c4e3eadc569ee4a8d31a4.png
[20200514085752714.png]: /images/20230312/b170c5db43a841a8a69949285720a473.png
[2020051409054641.png]: https://img-blog.csdnimg.cn/2020051409054641.png
[20200514100420614.png]: https://img-blog.csdnimg.cn/20200514100420614.png