分治算法-蒲公英云

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

基本思想

当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。

解题步骤

分治法解题的一般步骤：
（1）分解，将要解决的问题划分成若干规模较小的同类问题；
（2）求解，当子问题划分得足够小时，用较简单的方法解决；
（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

棋盘覆盖

题目：在一个(2^k)*(2^k)个方格组成的棋盘上，有一个特殊方格与其他方格不同，称为特殊方格，称这样的棋盘为一个特殊棋盘。我们要求对棋盘的其余部分用L型方块填满（注：L型方块由3个单元格组成。即围棋中比较忌讳的愚形三角，方向随意），且任何两个L型方块不能重叠覆盖。L型方块的形态如下：
题目的解法使用分治法，即子问题和整体问题具有相同的形式。我们对棋盘做一个分割，切割一次后的棋盘如图1所示，我们可以看到棋盘被切成4个一样大小的子棋盘，特殊方块必定位于四个子棋盘中的一个。假设如图1所示，特殊方格位于右上角，我们把一个L型方块（灰色填充）放到图中位置。这样对于每个子棋盘又各有一个“特殊方块”，我们对每个子棋盘继续这样分割，直到子棋盘的大小为1为止。

解题思路

分析：当k>0时，将2k×2k棋盘分割为4个2^k-1×2^k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。

实现：

每次都对分割后的四个小方块进行判断，判断特殊方格是否在里面。这里的判断的方法是每次先记录下整个大方块的左上角（top left coner）方格的行列坐标，然后再与特殊方格坐标进行比较，就可以知道特殊方格是否在该块中。如果特殊方块在里面，这直接递归下去求即可，如果不在，这根据分割的四个方块的不同位置，把右下角、左下角、右上角或者左上角的方格标记为特殊方块，然后继续递归。在递归函数里，还要有一个变量s来记录边的方格数，每次对方块进行划分时，边的方格数都会减半，这个变量是为了方便判断特殊方格的位置。其次还要有一个变nCount来记录L型骨牌的数量。
这里写图片描述

public class ChessBoradProblem { 
    private int[][] board;//棋盘
    private int specialRow;//特殊点的行下标
    private int specialCol;//特殊点的列下标
    private int size;
    private int type = 0;
    public ChessBoradProblem(int specialRow, int specialCol, int size) {
        super();
        this.specialRow = specialRow;
        this.specialCol = specialCol;
        this.size = size;
        board = new int[size][size];
    }
    /** * * @param specialRow 特殊点的行下标 * @param specialCol 特殊点的列下标 * @param leftRow 矩阵的左边起点行下标 * @param leftCol 矩阵左边起点的列下标 * @param size 矩阵的宽或者高 */
    private void ChessBoard(int specialRow,int specialCol,int leftRow,int leftCol,int size){
        if(size == 1){
            return;
        }
        int subSize = size/2;
        type = type%4 + 1;
        int n = type;
        //假设特殊点在左上角区域
        if(specialRow<leftRow+subSize&&specialCol<leftCol+subSize){
            ChessBoard(specialRow, specialCol, leftRow, leftCol, subSize);
        }else{
            //不在左上角，左上角矩阵的右下角就是特殊点
            board[leftRow+subSize-1][leftCol+subSize-1] = n;
            ChessBoard(leftRow+subSize-1, leftCol+subSize-1, leftRow, leftCol, subSize);
        }
        //特殊点在右上方
        if(specialRow<leftRow+subSize&&specialCol>=leftCol+subSize){
            ChessBoard(specialRow, specialCol, leftRow, leftCol+subSize, subSize);
        }else{
            board[leftRow+subSize-1][leftCol+subSize] = n;
            ChessBoard(leftRow+subSize-1, leftCol+subSize, leftRow, leftCol+subSize, subSize);
        }
        //特殊点在左下方
        if(specialRow>=leftRow+subSize&&specialCol<leftCol+subSize){
            ChessBoard(specialRow, specialCol, leftRow+subSize, leftCol, subSize);
        }else{
            board[leftRow+subSize][leftCol+subSize-1] = n;
            ChessBoard(leftRow+subSize, leftCol+subSize-1, leftRow+subSize, leftCol, subSize);
        }
        //特殊点在右下角
        if(specialRow>=leftRow+subSize&&specialCol>=leftCol+subSize){
            ChessBoard(specialRow, specialCol, leftRow+subSize, leftCol+subSize, subSize);
        }else{
            board[leftRow+subSize][leftCol+subSize] = n;
            ChessBoard(leftRow+subSize, leftCol+subSize, leftRow+subSize, leftCol+subSize, subSize);
        }
    }
    public void printBoard(int specialRow,int specialCol,int size){
        ChessBoard(specialRow, specialCol, 0, 0, size);
        printResult();
    }
    private void printResult() {
        for(int i = 0;i<size;i++){
            for(int j = 0;j<size;j++){
                System.out.print(board[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args){
        int N = 8;
        int specialRow = 0;
        int specialCol = 1;
        ChessBoradProblem boradProblem = new ChessBoradProblem(specialRow, specialCol, N);
        boradProblem.printBoard(specialRow, specialCol, N);
    }
}