算法课(7)

算法报告七 棋盘覆盖

                                                               16122020   钟顺源

一、题目大意

设n=$2^k$(k≥0)。在一个n×n个方格组成的棋盘中,恰有1个方格与其他方格不同,称该方格为特殊方格。显然,特殊方格在棋盘中可能出现的位置有4k种,因而有n2种不同的棋盘,下图所示是k=2,n=4时16种棋盘中的一个。

                                

在这里插入图片描述
棋盘覆盖问题要求用下图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
             在这里插入图片描述
易知,在任何一个n×n的棋盘中,用到的 L 型骨牌个数恰为 $(n^2-1)/3$。
你的任务是给定k>1,n=$2^k$设计一个算法实现棋盘的一种覆盖。

二、分析

对于要解决的问题,例如下述的一张图

将他分为四块,则左上角的一个小区域可以递归求解,那么其他区域呢?

只要在其他的方格的边界都加上一个黑块,就可以在填入一个黑块的前提下,将其他的区域也递归求解。

所以递归方程就是 T(n) = 4T(n/4)+O(1),复杂度为O(nlogn)。

问题就转换成了判断已经标号的方块在四个区域中的那个区域中。
递归到长度为1时就直接返回。

三、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
const int N=1e3;
int G[N][N];
int flag=0;
inline bool judge(int sx,int sy,int len,int bx,int by){
return sx<=bx&&bx<sx+len&&sy<=by&&by<sy+len;
}

void print(int sx,int sy,int k,int bx,int by){
if(k==0) return ;
int len=(1<<(k-1)); //四个小格子的尺寸
flag++;
int x1,y1;
if(judge(sx,sy,len,bx,by)) x1=bx,y1=by; //若已处理好的点在一号区,就记录这个坐标
else {x1=sx+len-1;y1=sy+len-1;G[x1][y1]=flag;} //若一号区没黑格,则为其右下角一个格子染色

int x2,y2;
if(judge(sx+len,sy,len,bx,by)) x2=bx,y2=by; //同理
else {x2=sx+len;y2=sy+len-1; G[x2][y2]=flag;} //......右上角

int x3,y3;
if(judge(sx,sy+len,len,bx,by)) x3=bx,y3=by;
else {x3=sx+len-1;y3=sy+len; G[x3][y3]=flag;} // ......左下角

int x4,y4;
if(judge(sx+len,sy+len,len,bx,by)) x4=bx,y4=by;
else {x4=sx+len;y4=sy+len; G[x4][y4]=flag;} // .....左上角

//递归的去处理这四个小方格,参数是已处理好的那个格子的坐标
print(sx,sy,k-1,x1,y1);
print(sx+len,sy,k-1,x2,y2);
print(sx,sy+len,k-1,x3,y3);
print(sx+len,sy+len,k-1,x4,y4);
}

int main()
{
int x,y,bx,by,k;
int cas=0;
while(~scanf("%d%d%d",&k,&bx,&by)){
memset(G,0,sizeof G);
flag=0;
printf("Case %d:n=%d\n",++cas,(1<<(k-1)));
print(1,1,k,bx,by);
for(int i=1;i<=(1<<k);i++)
for(int j=1;j<=(1<<k);j++){
if(i==bx&&j==by)printf(" #%c"," \n"[j==(1<<k)]);
else
printf("%2d%c",G[i][j]," \n"[j==(1<<k)]);
}
}
return 0;
}

四、运行结果

数据
1 2 1
2 2 3
3 1 1

五、实验体会

   这是个经典的递归程序,有很多的细节需要考虑,比如填色的计数器该如何设置,作为参数传递下去?还是作为一个全局变量?还有如何判断已经染色的方格的位置?虽然思路比较简单,但真正判断起来还是要非常仔细的,一些边界值要仔细的计算。

-------------本文结束-------------