棋盘覆盖问题

一. 问题描述

---

给定一个2k×2k的棋盘(具体图例见教材)，有一个特殊棋格，拥有一个特殊棋格的棋盘称为特殊棋盘。现要用四种L型骨牌(具体图例见教材)覆盖特殊棋盘上除特殊棋格外的全部棋格，不能重叠，找出覆盖方案。（使用二分法）

二. 审题

---

给一个2k * 2k的棋盘(k>=0)，棋盘中有一个特殊棋格。如图所示：

现在需要使用以下四种L型骨牌覆盖除特殊棋格外的全部棋盘，不能重叠。求解覆盖方案。

生活中，像布线时绕过障碍物或者铺地砖遇到障碍物都可以使用此算法来解决这类问题。

三. 问题建模

---

当n = 1 时，棋盘的大小为2*2，此时可以使用一个L型骨牌将棋盘可以被覆盖。如图所示：

假设n = k时，即棋盘大小为2k * 2k时，该问题有解。

则当n = k + 1时，即棋盘大小为2k+1 * 2k+1时时，我们可以将棋盘分为4个大小为2k * 2k子棋盘，其中一个子棋盘中包含特殊方格，至于其他3个不存在特殊方格的子棋盘，我们利用一个L型骨牌来覆盖这个3个子棋盘的交汇处，从而分别构造一个特殊的方格，将原问题转换为4个n = k时的子问题，因为n = k时有解，所以n = k + 1时也有解。如图所示：

介于上述思路，我们可以采用分治算法，将2k * 2k的棋盘覆盖问题分解为N个规模较小的子棋盘的覆盖问题，即求出子问题的解，就可以得到原问题的解。

分治算法的三个步骤：

① 分解：将原问题的分解成若干个小规模，相互独立，但与原问题形式一样的子问题。

② 解决：如果子问题规模小并且容易求解就可以直接求解，否则递归求解各子问题。

③ 合并：将各个子问题的解合并成原问题的解。

算法分析：

当n = 2k 时,

T(n) = O(n2) = O(4k)

四. 代码实现

---

package ch01;


import java.util.Scanner;

import static java.lang.Math.pow;

public class FillChess {
    private static int ChessSize;
    private static int x1,y1;
    private static int[][] chess;
    private static int t = 1;
    public static void main(String[] args) {
        ChessSize = (int) pow(2,new Scanner(System.in).nextInt());
        Scanner sc = new Scanner(System.in);
        String[] numbers = sc.nextLine().split(" ");
        x1=Integer.parseInt(numbers[0])-1;
        y1=Integer.parseInt(numbers[1])-1;
        chess = new int[ChessSize][ChessSize];
        three(0, 0, x1, y1, ChessSize);
        print();
    }

    private static void print() {
        for (int i = 0; i < ChessSize; i++) {
            for (int j = 0; j < ChessSize; j++) {
                if (i==x1 && j==y1) chess[i][j]=-1;
                System.out.print(chess[i][j] + "\t");
            }
            System.out.println();
        }
    }

    public static void three(int chess_h, int chess_l, int t_h, int t_l,int size) {
        //如果棋盘是1*1,则直接返回
        if (size == 1) return;
        //L牌号
        int num = t++;
        //分割棋盘
        int p = size / 2;
        //覆盖左上角棋盘
        if (t_h < chess_h + p && t_l < chess_l + p) {
            three(chess_h, chess_l, t_h, t_l, p);//有特殊
        } else {//无特殊
            //覆盖右下角
            chess[chess_h + p - 1][chess_l + p - 1] = num;
            three(chess_h, chess_l, chess_h + p - 1, chess_l + p - 1, p);
        }
        //覆盖右上角棋盘
        if (t_h < chess_h + p && t_l >= chess_l + p) {
            three(chess_h, chess_l + p, t_h, t_l, p);
        } else {//殊无特
            //覆盖左下角
            chess[chess_h + p - 1][chess_l + p] = num;
            three(chess_h, chess_l + p, chess_h + p - 1, chess_l + p, p);
        }
        //覆盖左下角棋盘
        if (t_h >= chess_h + p && t_l < chess_l + p) {
            three(chess_h + p, chess_l, t_h, t_l, p);//有特殊
        } else {
            //覆盖右上角
            chess[chess_h + p][chess_l + p - 1] = num;
            three(chess_h + p, chess_l, chess_h + p, chess_l + p - 1, p);
        }
        //覆盖右下角棋盘
        if (t_h >= chess_h + p && t_l >= chess_l + p) {
            three(chess_h + p, chess_l + p, t_h, t_l, p);//有特殊
        } else {
            //覆盖左上角
            chess[chess_h + p][chess_l + p] = num;
            three(chess_h + p, chess_l + p, chess_h + p , chess_l + p , p);
        }
    }
}

运行结果：