问题描述
有一个 x<img src="https://latex.codecogs.com/gif.latex?2%5Ek" alt="2^k" class="mathcode" />&nbsp;（k&gt;0）的棋盘，恰好有一个方格与其他方格不同，称之为特殊方格。现在要用如下图所示的L形骨牌覆盖除了特殊方格以外的其他全部方格，骨牌可以任意旋转，并且任何两个骨牌不能重复。请给出一种覆盖方式。
文章来源：https://www.toymoban.com/news/detail-425284.html
样例：
输入：
输出：
思路——分治法：
将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。
递归地解决这些子问题，然后将各个子问题的解合并得到原问题的解。
就是将规模为n的问题自顶向下分解，直到小问题分解到足够小，可以解决时，再自底向上合并，从而得到原来的解。
当k=0（棋盘只有1格），特殊点只能唯一，L骨牌数为0
当k >0，则可将 2*kⅹ2*k 棋盘分割为 4个 2*k-1ⅹ2*k-1 的子棋盘
判断特殊点在哪一个子棋盘中，用一块L骨牌放在其它三个子棋盘的连接处
以此类推，则最后可将每个子棋盘划分为1格的棋盘，结束递归
代码实现：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <iomanip>
using namespace std;
int arr[1000][1000];
int num = 0;
void ChessBoard(int x, int y, int a, int b, int length);
int main() {
//棋盘大小
int k;
int length;
cout << "请输入k：";
cin >> k;
length = pow(2,k);
//空白点坐标
int a, b;
cout << "请输入空格位置：";
cin >> a >> b;
cout << endl;
arr[a][b] = 0;//标点用0表示
ChessBoard(1, 1, a, b, length);
cout << setw(5);
for (int i = 1; i <= length; i++) {
for (int j = 1; j <= length; j++) {
cout << arr[i][j] << setw(5);
}
cout << endl;
}
return 0;
}
void ChessBoard(int x, int y, int a, int b, int length) {
if (length == 1) {
return;
}
int h = length / 2;//分割棋盘
int t = ++num;//骨牌号，从1开始,相同数字代表是同一块
//以“田”的左下角为（1,1）
//左下角
if (a < x + h && b < y + h) {
ChessBoard(x, y, a, b, h);
}
else {
arr[x + h - 1][y + h - 1] = t;
ChessBoard(x, y, x + h - 1, y + h - 1, h);
}
//左上角
if (a < x + h && b >= y + h) {
ChessBoard(x, y + h, a, b, h);
}
else {
arr[x + h - 1][y + h] = t;
ChessBoard(x, y + h, x + h - 1, y + h, h);
}
//右下角
if (a >= x + h && b < y + h) {
ChessBoard(x + h, y, a, b, h);
}
else {
arr[x + h][y + h - 1] = t;
ChessBoard(x + h, y, x + h, y + h - 1, h);
}
//右上角
if (a >= x + h && b >= y + h) {
ChessBoard(x + h, y + h, a, b, h);
}
else {
arr[x + h][y + h] = t;
ChessBoard(x + h, y + h, x + h, y + h, h);
}
}
参考资料：《计算机算法设计与分析（第四版）》 文章来源地址https://www.toymoban.com/news/detail-425284.html
到了这里，关于棋盘覆盖问题——分治法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
