算法设计与分析算法实现——棋盘覆盖问题

在一个2^k×2^k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一个特殊方格，且称该棋盘为一特殊棋盘，如图1所示，蓝色的为特殊方格：

要用图2中的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何两个L型骨牌不得重叠覆盖。
提示：使用分治法

这是分治法的典型问题，k>0时，可将2^k×2^k的棋盘划分为4个2^k-1×2^k-1的子棋盘，这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。

详细过程图：

#include
#include 
using namespace std;
int arr[16][16] = {
   0};//初始化棋盘每个方格都是0
void f(int rs,int re,int cs,int ce,int r,int c,int n) {
   //rs是行初始，re是行末尾，cs是列初始，ce是列末尾，(r,c)是特殊方格的下标，n是特殊方格的标号
	if (rs==re) {
   //递归出口，棋盘只有一个方格
		return;
	}
	int ra = (rs + re - 1) / 2;
	int ca = (cs + ce - 1) / 2;
	int rb = (rs + re 
1
2
3
4
5
6
7
8
9
10
11
12
13