本文主要是介绍分治法，棋盘覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//分治法--棋盘覆盖问题
//问题描述：在一个2k x 2k ( 即：2^k x 2^k )个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，
//且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用4不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，
//且任何2个L型骨牌不得重叠覆盖。
//思想：将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，
//将他们中的也假一个方格设为特殊方格。如果是：
//左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格
//右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格
//左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格
//右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格
//当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。
//这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
//算法说明：用一个二维整形数组board表示棋盘，board【0】【0】是棋盘左上角方格，
//tile是算法中的一个全局整型变量，用来表示骨牌编号，初始值为0
//参数：tr是棋盘左上角的方格行号
// tc是棋盘左上角的方格列号
// dr是特殊方格所在行号
// dc是特殊放个所在列号
// size是2^k,棋盘是 2^k*2^k的
// 此程序可以实现检测是否可以覆盖
// 因为骨牌个数是4^k/3,只需检测是否是整数
//本题即使要求，将图形分割，变为4个格子的大小，然后4个格子中有一个被覆盖，另外3个格子被新的一个覆盖
#include<iostream>
#include<iomanip>
using namespace std;
int board[8][8]={0};
int tile=1; //tile骨牌编号
void chessboard(int tr,int tc,int dr,int dc,int size)//左上行号，左上列号，特殊行号，特殊列号，棋盘大小
{
if(size==1)return;
int t=tile++; //编号加1
int s=size/2; // 规模缩小
//左上角
if(dr<tr+s&&dc<tc+s)//特殊行小于左上行+规模...确定特殊格子在左上位置
chessboard(tr,tc,dr,dc,s); //继续分割，找到位置
else
{
board[tr+s-1][tc+s-1]=t; //若不在左上区间，在左上区域最下边角落 覆盖
chessboard(tr,tc,tr+s-1,tc+s-1,s); //继续调用
}
//分别对左上，左下，右上，右下位置寻找或覆盖，直至k==1停止
//右上角
if(dc>=tc+s&&dr<tr+s)
chessboard(tr,tc+s,dr,dc,s);
else
{
board[tr+s-1][tc+s]=t;
chessboard(tr,tc+s,tr+s-1,tc+s,s);
}
//左下角
if(dr>=tr+s&&dc<tc+s)
chessboard(tr+s,tc,dr,dc,s);
else
{
board[tr+s][tc+s-1]=t;
chessboard(tr+s,tc,tr+s,tc+s-1,s);
}
//右上角
if(dc>=tc+s&&dr>=tr+s)
chessboard(tr+s,tc+s,dr,dc,s);
else
{
board[tr+s][tc+s]=t;
chessboard(tr+s,tc+s,tr+s,tc+s,s);
}
}
int main()
{
chessboard(0,0,0,7,8); //特殊格子位置，在[0,7],图形规模为2的3次方
for(int i=0 ; i<8 ; i++)
for(int j=0 ; j<8 ; j++)
{
cout << setw(3) << board[i][j];
if(j==7)
cout << endl ;
}
return 0;
}
//输出即为格子覆盖状况，同一标号为同一图形
//fout<<setw(x)<<n（x>0）相对于右对齐x位
//cout<<setw(x)<<n（x<0）相对于左对齐-x位
这篇关于分治法，棋盘覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
