问题描述
在一个\({2^k} \times {2^k}(K \geqslant 0)\) 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。 棋盘覆盖问题要求用图所示的4种不同形状的\(L\)型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个\(L\)型骨牌不得重叠覆盖。
问题分析
算法设计
算法主要实现两个状态：
-
有特殊方格的棋盘
如果棋盘大小大于1*1，那么对棋盘进行划分，使 的棋盘划分为四个 的子棋盘，其中有一个是有特殊方格的子棋盘，有三个是无特殊方格的子棋盘。 -
无特殊方格的棋盘
情况二还分以下四个情况：
2.1. 是未划分前棋盘的左上子棋盘：将最右下格填充为特殊方格
2.2. 是未划分前棋盘的右上子棋盘：将最左下格填充为特殊方格
2.3. 是未划分前棋盘的左下子棋盘：将最右上格填充为特殊方格
2.4. 是未划分前棋盘的右下子棋盘：将最左上格填充为特殊方格
之后按照情况一继续划分。
可以采用分治的思想进行算法设计，解决这个问题需要如下变量及函数。 -
棋盘：表示为一个二维数组chess[][]，大小由题目要求限制。
-
骨牌：骨牌需要在函数里填充，每次完整调用一个函数，视作填充一个骨牌，用cnt变量来作为骨牌标识。
-
填充函数：用get_chess表示填充函数，包括形参：
3.1. tr——当前状态棋盘的左上角行号
3.2. tc——当前状态棋盘的左上角列号
3.3. dr——特殊方格的行号
3.4. dc——特殊方格的列号
3.5. k——棋盘的规模
函数的作用包括：划分、填充与合并。
算法复杂度分析
时间复杂度
从分治策略的角度可以看出，该算法满足以下递归方程
\[T(k)= \begin{cases} O(1) , & k = 0\\ 4T(k-1)+O(1),& k>0 \end{cases} \]解该递归方程可以得出，该算法的时间复杂度为
\(T(K)=O(4^k)\)
算法实现
棋盘覆盖代码
#include <iostream>
#include <algorithm>
#include <iomanip>
#define MAXN 16385
using namespace std;
int chess[MAXN][MAXN];
int cnt = -1;//棋子标记
void get_chess(const int &tr/*左上*/, const int &tc/*左上*/, const int &k/*规模*/,
const int &dr, const int &dc) {
if (k == 1) return;//最小子问题
int size = k / 2;//规模划分
int _tr = tr;
int _tc = tc;
int L = ++cnt;
//左上
if (dc >= _tc && dr >= _tr && dr < _tr + size && dc < _tc + size)//特殊方格
{
get_chess(_tr, _tc, size, dr, dc);
} else {
chess[_tr + size - 1][_tc + size - 1] = L + '0';//标记右下角
get_chess(_tr, _tc, size, _tr + size - 1, _tc + size - 1);
}
//右上
_tr = tr;
_tc = tc + size;
if (dc >= _tc && dr >= _tr && dr < _tr + size && dc < _tc + size)//特殊方格
{
get_chess(_tr, _tc, size, dr, dc);
} else {
chess[_tr + size - 1][_tc] = L + '0';//标记左下角
get_chess(_tr, _tc, size, _tr + size - 1, _tc);
}
_tr = tr + size;
_tc = tc;
if (dc >= _tc && dr >= _tr && dr < _tr + size && dc < _tc + size)//特殊方格
{
get_chess(_tr, _tc, size, dr, dc);
} else {
chess[_tr][_tc + size - 1] = L + '0';//标记右上角
get_chess(_tr, _tc, size, _tr, _tc + size - 1);
}
//右下
_tr = tr + size;
_tc = tc + size;
if (dc >= _tc && dr >= _tr && dr < _tr + size && dc < _tc + size)//特殊方格
{
get_chess(_tr, _tc, size, dr, dc);
} else {
chess[_tr][_tc] = L + '0';//标记左上角
get_chess(_tr, _tc, size, _tr, _tc);
}
}
int main() {
int k, dr, dc;
cin >> k >> dr >> dc;
chess[dr + 1][dc + 1] = 'd';
get_chess(1, 1, 1 << k, dr + 1, dc + 1);
for (int i = 1; i <= 1 << k; i++) {
for (int j = 1; j <= 1 << k; j++) {
cout << setfill(' ') << setw(4) << chess[i][j];
}
cout << '\n';
}
return 0;
}