在一个2 ^k ×2^ k 个方格组成的棋盘中，恰有一个方格与其他方格不同,，称该方格为一特殊方格,且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
思路如下，将棋盘十字分成4份为2^(k-1) x 2^(k-1)大小的小棋盘，其中特殊方格必在其中一个区域，另外三个区域则是完整空白的，
因此可以选用上诉L型骨牌中的一块放在中间，恰好覆盖到另外三个空白区域，如此，就变成了4个和最开始一样的问题，然后又是中间十字分……
禁止套娃！！！
可以在白纸上画一画玩玩就明白了，然后我用的Java实现了一遍（其实就是大概抄了一下老师的课件）
1 import java.util.Scanner; 2 3 /** 4 * @author: Davion 5 * @date: 2020/3/14 6 * @description: 棋盘覆盖问题，分治算法 7 */ 8 public class Chess { 9 private static int title = 1; 10 private static int[][] border =new int[64][64]; 11 public static void main(String[] args) { 12 Scanner scanner = new Scanner(System.in); 13 int size, dx, dy; 14 // 输入对应数据 15 System.out.print("size:"); 16 size = scanner.nextInt(); 17 System.out.print("x, y:"); 18 dx = scanner.nextInt(); 19 dy = scanner.nextInt(); 20 21 // 设置特殊位置 22 border[dx][dy] = -1; 23 chessBord(0, 0, dx, dy, size); 24 25 for (int i = 0; i < size; i++) { 26 for (int j = 0; j < size; j++) { 27 System.out.printf("%3s", border[i][j]); 28 } 29 System.out.println(); 30 } 31 } 32 33 /** 34 * 35 * @param tx 左上x坐标 36 * @param ty 左上y坐标 37 * @param dx 不可覆盖旗子x坐标 38 * @param dy 不可覆盖旗子y坐标 39 * @param size 棋盘大小 40 */ 41 private static void chessBord(int tx, int ty, int dx, int dy, int size){ 42 if (size == 1){ 43 return; 44 } 45 int t = title++; 46 int s = size / 2; 47 // 覆盖左上 48 if (dx < tx + s && dy < ty + s) { 49 // 特殊点在左上 50 chessBord(tx, ty, dx, dy, s); 51 } else { 52 // 特殊点不在左上 53 border[tx + s - 1][ty + s - 1] = t; 54 chessBord(tx, ty, tx + s - 1, ty + s - 1, s); 55 } 56 57 // 覆盖左下 58 if (dx >= tx + s && dy < ty + s) { 59 chessBord(tx + s, ty, dx, dy, s); 60 } else { 61 border[tx + s][ty + s - 1] = t; 62 chessBord(tx + s, ty, tx + s, ty + s - 1, s); 63 } 64 65 if (dx < tx + s && dy >= ty + s) { 66 chessBord(tx, ty + s, dx, dy, s); 67 } else{ 68 border[tx + s - 1][ty + s] = t; 69 chessBord(tx, ty + s, tx + s - 1, ty + s, s); 70 } 71 72 if (dx >= tx + s && dy >= ty + s) { 73 chessBord(tx + s, ty + s, dx, dy, s); 74 } else { 75 border[tx + s][ty + s] = t; 76 chessBord(tx + s, ty + s, tx + s, ty + s, s); 77 } 78 } 79 }
这里的x和y我搞混了，想的是平时数学用的横向x，纵向y，实际上这里的x是指地图的行号，y是地图的列号，
所以写的时候一开始预想的填图顺序为左上，右上，左下，右下，实际出来的顺序是左上，左下，右上，右下
