棋盘覆盖问题
棋盘覆盖问题在物理世界的应用
-
房间铺瓷砖，要绕开某处（前提是他不把瓷砖切了）；
-
并行激光手术；
-
你们想想吧，有想法私信一下我。
问题描述
在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何k≥0,有4^k种不同的特殊棋盘. 下图中的特殊棋盘是当k=3时16个特殊棋盘中的一个：
题目要求在棋盘覆盖问题中,要用下图所示的4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖.
如何证明该问题有解
用数学归纳法
-
当k = 0时（1 × 1的棋盘），及特殊方格，骨牌数为0；
-
k > 0时
（1） 将2^k × 2^k的棋盘划分为4个2^（k-1）×2^（k-1）的子棋盘；
（2） 在递归之前要将原问题转化为4个较小规模的相同子问题；
（3） 用一个骨牌覆盖这三个棋盘的汇合处；
（4） 递归使用这种分割直至缩小到1 × 1。
算法实现
-
棋盘：可以用一个二维数组board[SIZE] [SIZE]表示一个棋盘，其中，size=2^k。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量；
-
子棋盘：整个棋盘用二维数组board[SIZE] [SIZE]表示，其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示；
-
特殊方格：用board[x] [y]表示特殊方格，x和y是该特殊方格在二维数组board中的下标;
-
L型骨牌：一个2^k×2^k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4^k-1)/3，将所有L型骨牌从1开始连续编号，用一个全局变量t = 0表示。
#include<iostream>
#include<algorithm>
#include<cmath>
#define SIZE 1024
using namespace std;
unsigned int board[SIZE][SIZE];//棋盘的大小
int ID = 0;
void ChessBoard(int tc, int tr, int x, int y, int size) //棋盘的行列，特殊棋盘的行列，分割的大小
{
if (size == 1)//设置阈值，当大小是1，也就是一个方块的时候直接退出，因为不能再切了
return;
int s = size / 2;// 二分了，大小是原来的一半，棋盘上表现为被切成了大小相同的四分部
int id = ++ID; //当前棋盘需要覆盖的id号
//*************特殊方块在左上角
if (x < tc+s && y < tr+s){ //在
ChessBoard(tc, tr, x, y, s);//注意size减半了
}
else{//右下角标记id号
board[tc+s-1][tr+s-1]=id;
ChessBoard (tc, tr, tc+s-1, tr+s-1, s);
}
//************特殊方块在右上角
if (x >= tc+s && y < tr+s){//在
ChessBoard(tc+s, tr, x, y, s);//注意size减半了
}
else{//左下角标记id号
board[tc+s][tr+s-1]=id;
ChessBoard (tc+s, tr, tc+s, tr+s-1, s);
}
//************特殊方块在左下角
if (x < tc+s && y >= tr+s){//在
ChessBoard(tc, tr+s, x, y, s);//注意size减半了
}
else{//右下角标记id号
board[tc+s-1][tr+s]=id;
ChessBoard (tc, tr+s, tc+s-1, tr+s, s);
}
//************特殊方块在右下角
if (x >= tc+s && y >= tr+s){//在
ChessBoard(tc+s, tr+s, x, y, s);//注意size减半了
}
else{
board[tc+s][tr+s]=id;
ChessBoard (tc+s, tr+s, tc+s, tr+s, s);
}
}
int main(){
int k, dr, dc, x, y, size;
cin >> k >> x >> y;
size = pow(2, k);
ChessBoard(0, 0, x, y, size);
cout<<ID<<endl;
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
cout<<board[j][i]<<" ";
}
cout<<endl;
}
return 0;
}
算法分析
T(k)满足如下递推式：
-
当k = 0时,T(k) = 1
-
当k > 0时,T(k) = 4T(k-1)
解此递推式可得T(k) = O(4^k)