大多数勤奋的学生，学不好，很可能是：老师不会教。 ---老洋
一、问题描述
棋盘覆盖问题：
1、要求在2^k * 2^k 个方格组成的棋盘中，
2、你给定任意一个特殊点，用一种方案实现对除该特殊点的棋盘实现全覆盖。
二、什么是：分治算法， 棋盘中如何用？
分治算法（通俗的讲）：
1、大问题，分解为小问题。
2、分解的（小问题之间）互相不重叠
3、小问题和大问题（是同类型问题），只是规模不一样。
三、问题讲解：视频推荐
可以结合着看：第一个（视频）图很生动， 第二个视频（分析复杂度，很透彻）， 首推（第二个）
视频一：https://www.bilibili.com/video/BV1vt4y1i7VF/?spm_id_from=333.788.videocard.5
视频二：https://www.bilibili.com/video/BV1o7411Q7GV/?spm_id_from=333.788.videocard.4
四、博客推荐
博客一：注重（理解问题）
博客二：注重（实现代码）
五、代码实现C 和 Java版本
1、C版本（visual studio 2019编译器）
注意：因为visual studio 用scanf() 被认为不安全，此处用了scanf_s(), 其余编译器，修改下，即可
①、代码
#include <stdio.h>
#include<math.h>
static int tile = 1; //L骨牌：开始的值
const int BOARD_SIZE = 64; //棋盘的：最大值 64 * 64
static int board[BOARD_SIZE][BOARD_SIZE] = { 0 }; //初始化棋盘：行BOARD_SIZE * 列BOARD_SIZE
//tr, tc起始点， dr，dc(特殊点), size棋盘行、列大小
void chess_board(int tr, int tc, int dr, int dc, int size) {
//1、检验：size 是否为1， 若为1, 则说明（1 * 1）棋盘， 只有一个格子（该格子就是：特殊点），不用覆盖
if (size == 1) {
return;
}
//2、骨牌L存放的数字：自增
int t = tile++; //切记：t为作为标志当前骨牌（存放的数字），tile自增是因为：方便递归
//3、将当前棋盘：分割成四块， 利用（分治算法）， 分治算法：问题划分为（同种问题、且问题不重复）
int sz = size / 2; //分割后的大小为：(2^k - 1) * (2^k - 1)
//4、判断：特殊点在，左上（分块）吗？
if (dr < tr + sz && dc < tc + sz) { //此时（特殊点）在：左上分块
chess_board(tr, tc, dr, dc, sz); //继续：分割棋盘，用L型骨牌（覆盖）
}
else {
board[tr + sz - 1][tc + sz - 1] = t; //将：特殊结点外的，毗连（左上结点）赋上骨牌值
chess_board(tr, tc, tr + sz - 1, tc + sz - 1, sz); //将该毗连结点，作为新的特殊点：递归
}
//5、判断：特殊点在，右上（分块）吗？
if (dr < tr + sz && dc >= tc + sz) { //此时：特殊点在(右上角块)
chess_board(tr, tc + sz, dr, dc, sz); //初始值的变更：总在该方格的（左上角顶）
}
else {
board[tr + sz - 1][tc + sz] = t;
chess_board(tr, tc + sz, tr + sz - 1, tc + sz, sz);
}
//6、判断：特殊点在，左下（分块）吗？
if (dr >= tr + sz && dc < tc + sz) { //此时：特殊点在（左下块）
chess_board(tr + sz, tc, dr, dc, sz);
}
else {
board[tr + sz][tc + sz - 1] = t;
chess_board(tr + sz, tc, tr + sz, tc + sz - 1, sz);
}
//7、判断：特殊点在，右下（分块）吗？
if (dr >= tr + sz && dc >= tc + sz) { //此时：特殊点在（右下块）
chess_board(tr + sz, tc + sz, dr, dc, sz);
}
else {
board[tr + sz][tc + sz] = t;
chess_board(tr + sz, tc + sz, tr + sz, tc + sz, sz);
}
}
void print_chess(int size) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
printf("%4d", board[i][j]);
}
printf("\n");
}
}
//通过输入k值：获取棋盘大小
int getSize() {
//1、请输入：棋盘大小2^k中的（k值）
int k = 0;
printf("请输入 k = ");
scanf_s("%d", &k);
//2、判断：k是否大于6 (因为我：设置了最大棋盘为 64 * 64)
int size = 1; //棋盘：行、列值（棋盘是一个：矩阵）
while (true) {
if (k < 0 || k > 6) {
printf("您的k值有误，请输入 k = ");
scanf_s("%d", &k);
}
else {
size = pow(2, k);
break;
}
}
//3、打印棋盘大小， 并返回
printf("您的棋盘大小为：%d * %d\n", size, size);
return size;
}
//设置：起初，棋盘的（特殊点）的坐标（从索引0开始）
void setSpecialPot(int* x1, int* y1, int size) {
int x;
int y;
while (true) {
printf("请输入(特殊点)的 x = ");
scanf_s("%d", &x);
printf("请输入(特殊点)的 y = ");
scanf_s("%d", &y);
if (x >= 0 && x <= size - 1 && y >= 0 && y <= size - 1) {
break;
}
else {
printf("您的x, y值（越界）, 请重新输入：\n");
}
}
*x1 = x;
*y1 = y;
}
int main(void) {
//1、获取棋盘大小
int size = getSize();
//2、请输入：初始（特殊点）
int x;
int y;
setSpecialPot(&x, &y, size);
//3、进行棋盘覆盖
chess_board(0, 0, x, y, size); //覆盖棋盘
//4、打印棋盘
print_chess(size);
}
②、代码图
③、运行结果
2、Java版本（已封装, Intellij编译器）
已封装版本：看起来清爽，理解起来可能要（想一想）
①、代码
package com.yyy.test;
import java.util.Scanner;
/**
* 分治法——棋盘覆盖问题
* 棋盘覆盖问题：描述
* <1>、有一个2^k∗2^k的(方格棋盘)，(只有1个)方格是黑色的，其他为白色。
* <2>、你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖，
* <3>、且任意一个白色方格（不能同时）被（两个或更多牌）覆盖。
*/
public class ChessBoard01 {
public int board[][]; //棋盘：引用
private int boardSize; //棋盘大小
private int tile; //L骨牌：存放值
private int SpecialX; //特殊方格：行索引
private int SpecialY; //特殊方格：列索引
public ChessBoard01() {
//获取：棋盘大小
boardSize = getBoardSize();
//初始化：棋盘
board = new int[boardSize][boardSize];
//初始化：特殊方格
initSpecial();
//初始化：骨牌值
tile = 1; //骨牌值：从1开始
}
/**
* 该方法：利用分治思想，大问题分解成（同一类型的：小问题）， 小问题之间（没有交叉）进行（棋盘覆盖）
* @param tr: 初始（查找点）行索引
* @param tc：初始（查找点）列索引
* @param dr：初始（特殊方格）行索引
* @param dc：初始（特殊方格）列索引
* @param initSize：初始（棋盘大小），initSize * initSize (矩阵棋盘)
*/
public void chessBoard(int tr, int tc, int dr, int dc, int initSize){
//1、判断：当棋盘只有（1个方格时），不用覆盖， 因为该方格，必为（特殊方格）
if(initSize == 1){
return; //此时是：递归出口
}
//2、创建：骨牌序号（L骨牌由3个方格组成），这3个方格（值一样）
int tileSeque = tile++; //tile值：后置递增，是为了（递归覆盖）方便
//3、将棋盘分4块： 大小变为 (2^k)-1 * (2^k)-1
int size = initSize / 2;
//4、判断：（特殊方格）是否在(左上分块)
if(dr < tr+size && dc < tc+size){ //此时：（特殊方格）在（左上分块）中
chessBoard(tr, tc, dr, dc, size); //直接：递归（左上分块）
}else{
this.board[tr+size-1][tc+size-1] = tileSeque; //此时：特殊方格（不在，左上分块中），为小问题（生成：特殊方格）
chessBoard(tr, tc, tr+size-1, tc+size-1, size); //小问题：分块，覆盖
}
//5、判断：（特殊方格）是否在(右上分块)
if(dr < tr+size && dc >= tc+size){ //此时：（特殊方格）在（右上分块中）
chessBoard(tr, tc+size, dr, dc, size); //直接：递归（右上分块）
}else{
this.board[tr+size-1][tc+size] = tileSeque; //此时：特殊方格（不在，右上分块中），为小问题（生成：特殊方格）
chessBoard(tr, tc+size, tr+size-1, tc+size, size); //小问题：分块，覆盖
}
//6、判断：（特殊点）是否在(左下分块)
if(dr >= tr+size && dc < tc+size){ //此时：特殊方格，在左下分块中
chessBoard(tr+size, tc, dr, dc, size); //直接：递归（左下分块）
}else{
this.board[tr+size][tc+size-1] = tileSeque; //此时：特殊方格（不在，左下分块中），为小问题（生成：特殊方格）
chessBoard(tr+size, tc, tr+size-1, tc+size-1, size); //小问题：分块，覆盖
}
//7、判断：（特殊点）是否在(右下分块)
if(dr >= tr+size && dc >= tc+size){ //此时：特殊方格，在右下分块中
chessBoard(tr+size, tc+size, dr, dc, size); //直接：递归（右下分块）
}else{
this.board[tr+size][tc+size] = tileSeque; //此时：特殊方格（不在，右下分块中），为小问题（生成：特殊方格）
chessBoard(tr+size, tc+size, tr+size, tc+size, size);
}
}
//获取：棋盘大小
public int getBoardSize(){
//1、设置：扫描（控制台）输入内容
Scanner stdIn = new Scanner(System.in);
//2、输入棋盘（2^k）*（2^k）中的：k值
System.out.print("请输入,指数幂（整数） k = ");
int k = stdIn.nextInt();
//3、通过k值：获取（矩阵棋盘）大小
int size = (int)Math.pow(2, k);
System.out.println("棋盘大小为：" + size + " * " + size);
return size;
}
//初始化：特殊方块
public void initSpecial(){
Scanner stdIn = new Scanner(System.in);
//4、输入：棋盘（特殊方格）的（索引坐标）
System.out.print("请输入，特殊方格（行坐标） x = ");
int x = stdIn.nextInt();
System.out.print("请输入，特殊方格（列坐标） y = ");
int y = stdIn.nextInt();
while (true){
if(x >= 0 && x <= boardSize-1 && y >= 0 && y <= boardSize-1){ //检测（特殊方格）坐标是否越界
break; //坐标没有越界
}else{
System.out.println("特殊方格，初始化坐标越界，请重新输入：");
System.out.print("请输入，特殊方格（行坐标） x = ");
x = stdIn.nextInt();
System.out.print("请输入，特殊方格（列坐标） y = ");
y = stdIn.nextInt();
}
}
SpecialX = x;
SpecialY = y;
}
//间接调用：覆盖棋盘
public void chessBoardStart(){
chessBoard(0, 0, SpecialX, SpecialY, boardSize);
}
//打印：打印棋盘内容
public void printBoard(){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board.length; j++){
System.out.print(board[i][j] + "\t");
}
System.out.println(""); //换行
}
}
//主方法
public static void main(String[] args){
//1、创建：棋盘对象
ChessBoard01 board = new ChessBoard01();
//2、进行覆盖
board.chessBoardStart();
//3、打印：覆盖后的棋盘内容
board.printBoard();
}
}
②、代码图
③、运行结果
3、Java版本（未封装）
未封装版本：理解起来可能更简单
①、代码
package com.yyy.test;
import java.util.Scanner;
/**
* 分治法——棋盘覆盖问题
* 棋盘覆盖问题：描述
* <1>、有一个2^k∗2^k的(方格棋盘)，(只有1个)方格是黑色的，其他为白色。
* <2>、你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖，
* <3>、且任意一个白色方格（不能同时）被（两个或更多牌）覆盖。
*/
public class ChessBoard {
public int board[][]; //棋盘：大小
private int tile; //L骨牌：存放值
public ChessBoard(int size, int tile) {
this.board = new int[size][size]; //初始化棋盘大小：为2^k * 2^k 大小
this.tile = tile; //初始化L骨牌：存放值
}
/**
* 该方法：利用分治思想，大问题分解成（同一类型的：小问题）， 小问题之间（没有交叉）进行（棋盘覆盖）
* @param tr: 初始（查找点）行索引
* @param tc：初始（查找点）列索引
* @param dr：初始（特殊方格）行索引
* @param dc：初始（特殊方格）列索引
* @param initSize：初始（棋盘大小），initSize * initSize (矩阵棋盘)
*/
public void chessBoard(int tr, int tc, int dr, int dc, int initSize){
//1、判断：当棋盘只有（1个方格时），不用覆盖， 因为该方格，必为（特殊方格）
if(initSize == 1){
return; //此时是：递归出口
}
//2、创建：骨牌序号（L骨牌由3个方格组成），这3个方格（值一样）
int tileSeque = tile++; //tile值：后置递增，是为了（递归覆盖）方便
//3、将棋盘分4块： 大小变为 (2^k)-1 * (2^k)-1
int size = initSize / 2;
//4、判断：（特殊方格）是否在(左上分块)
if(dr < tr+size && dc < tc+size){ //此时：（特殊方格）在（左上分块）中
chessBoard(tr, tc, dr, dc, size); //直接：递归（左上分块）
}else{
this.board[tr+size-1][tc+size-1] = tileSeque; //此时：特殊方格（不在，左上分块中），为小问题（生成：特殊方格）
chessBoard(tr, tc, tr+size-1, tc+size-1, size); //小问题：分块，覆盖
}
//5、判断：（特殊方格）是否在(右上分块)
if(dr < tr+size && dc >= tc+size){ //此时：（特殊方格）在（右上分块中）
chessBoard(tr, tc+size, dr, dc, size); //直接：递归（右上分块）
}else{
this.board[tr+size-1][tc+size] = tileSeque; //此时：特殊方格（不在，右上分块中），为小问题（生成：特殊方格）
chessBoard(tr, tc+size, tr+size-1, tc+size, size); //小问题：分块，覆盖
}
//6、判断：（特殊点）是否在(左下分块)
if(dr >= tr+size && dc < tc+size){ //此时：特殊方格，在左下分块中
chessBoard(tr+size, tc, dr, dc, size); //直接：递归（左下分块）
}else{
this.board[tr+size][tc+size-1] = tileSeque; //此时：特殊方格（不在，左下分块中），为小问题（生成：特殊方格）
chessBoard(tr+size, tc, tr+size-1, tc+size-1, size); //小问题：分块，覆盖
}
//7、判断：（特殊点）是否在(右下分块)
if(dr >= tr+size && dc >= tc+size){ //此时：特殊方格，在右下分块中
chessBoard(tr+size, tc+size, dr, dc, size); //直接：递归（右下分块）
}else{
this.board[tr+size][tc+size] = tileSeque; //此时：特殊方格（不在，右下分块中），为小问题（生成：特殊方格）
chessBoard(tr+size, tc+size, tr+size, tc+size, size);
}
}
//打印：打印棋盘内容
public void printBoard(){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board.length; j++){
System.out.print(board[i][j] + "\t");
}
System.out.println(""); //换行
}
}
//获取棋盘大小
//主方法
public static void main(String[] args){
//1、设置：扫描（控制台）输入内容
Scanner stdIn = new Scanner(System.in);
//2、输入棋盘（2^k）*（2^k）中的：k值
System.out.print("请输入,指数幂（整数） k = ");
int k = stdIn.nextInt();
//3、通过k值：获取（矩阵棋盘）大小
int size = (int)Math.pow(2, k);
System.out.println("棋盘大小为：" + size + " * " + size);
//4、输入：棋盘（特殊方格）的（索引坐标）
System.out.print("请输入，特殊方格（行坐标） x = ");
int x = stdIn.nextInt();
System.out.print("请输入，特殊方格（列坐标） y = ");
int y = stdIn.nextInt();
while (true){
if(x >= 0 && x <= size-1 && y >= 0 && y <= size-1){ //检测（特殊方格）坐标是否越界
break; //坐标没有越界
}else{
System.out.println("特殊方格，初始化坐标越界，请重新输入：");
System.out.print("请输入，特殊方格（行坐标） x = ");
x = stdIn.nextInt();
System.out.print("请输入，特殊方格（列坐标） y = ");
y = stdIn.nextInt();
}
}
//5、创建：棋盘对象
ChessBoard board = new ChessBoard(size, 1);
//6、进行覆盖
board.chessBoard(0, 0, x, y, size);
//7、打印：覆盖后的棋盘内容
board.printBoard();
}
}