俞鑫《棋盘中的棋盘——浅谈棋盘的分割思想》

《俞鑫《棋盘中的棋盘——浅谈棋盘的分割思想》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、棋盘中的棋盘——浅谈棋盘的分割思想上海市复旦附中俞鑫信息学是一门综合性的学科，也是一门充满乐趣的学科。棋盘，作为一个重要的数学模型，以其趣味性和复杂的数学特性经常受到出题者的青睐。因此，深入研究棋盘中蕴含的算法思想对于一名信息学爱好者而言是十分必要的。在此，我将着重说明棋盘中的一种重要思想——棋盘的分割思想。引言子棋盘3子棋盘2子棋盘1对于一个m×n的棋盘，它所含的子棋盘共有Cm×Cn个，而其分割方法更是不计其数。巧妙地对棋盘进行分割，可以解决许多种类的棋盘问题。22引言例一：棋盘覆盖（经典问题)题目描述：在一个2k×2

2、k方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有4k种情形。因而对任何k≥0，有4k种不同的特殊棋盘。图中的特殊棋盘是当k=2时16个特殊棋盘中的一个。在棋盘覆盖问题中，我们要用以下4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。现求一种覆盖方法。4种不同形态的L型骨牌输入：第一行为k（棋盘的尺寸），第二行为x,y(1≤x,y≤2k)，分别表示特殊方格所在行与列。输出：共2k行，每行2

3、k个数，分别表示覆盖该格的L型的编号（特殊格用0表示）。输入：212输出：1022113243354455样例：算法分析由棋盘尺寸为2k×2k，我们可以想到将其分割成四个尺寸为2k-1×2k-1的子棋盘可是，由于含特殊方格的子棋盘与其它子棋盘不同，问题还是没有解决。算法分析只要稍作思考，我们就可以发现，只要将L型如图放置在棋盘的中央，就可以使四个子棋盘都变成特殊棋盘。此时问题也变成了四个相同的子问题，只需运用简单的递归就可以解决这道问题了。程序实现二位数组num:覆盖该格的L型的编号，下文所说的对方格赋值即对其对应的nu

4、m赋值。x1,y1:当前棋盘左上角方格的行号与列号x2,y2:当前棋盘右下角方格的行号与列号x3,y3:当前棋盘中特殊格的行号与列号ck:当前棋盘的尺寸（2ck×2ck）cnum:当前L型骨牌的编号初始值：x1y1x2y2x3y3ckcnum112k2kxyk1开始时，将num[x,y]设为0当ck=0时：棋盘尺寸为1×1，该格为已赋值的特殊格，不进行任何操作。当ck>0时：设xm为(x1+x2+1)/2，ym为(y1+y2+1)/2，xmymx1x2y1y2比较x3与xm，y3与ym的大小就能知道特殊格所在子棋盘的位置

5、，将另外三个子棋盘中靠近棋盘中央的三个方格赋值为cnum，并分别作为这三个子棋盘的特殊格。随后cnum增加1。再对这四个棋盘分别进行处理。程序实现时间复杂度：O(4k)复杂度分析空间复杂度：O(4k)由于覆盖一个2k×2k棋盘所需的L型骨牌个数为(4k–1)/3，故该算法是一个在渐进意义下最优的算法。小结将棋盘分割成子棋盘，要遵循以下两点：1.分割出的棋盘要与原棋盘尽可能相像。2.将原棋盘分割后尽量不要留下剩余部分。但如果分割后必定留下剩余部分又该如何呢下面这道例题就是用来解答这个问题的。例二：孔明棋问题（URAL105

6、1）题目描述：在一个无限大的棋盘的格子上有一些棋子，这些棋子构成一个m×n的矩形(m为高度，n为宽度且1≤m,n≤1000)。你可以用一个棋子跳过另一个相邻的棋子，被跳过的棋子将被移去，请你求出最少能剩下几个棋子。输入：m,n输出：最少能剩下的棋子数一种移动方法样例：输入：34输出：2下面是样例的一种走法：算法分析由于m=1或n=1的情况比较特殊，我们先处理m,n≥2的情况。为了叙述方便，我们称由棋子所在格子组成的棋盘为“真棋盘”。通过样例，我们可以发现，对于图(a)中位于4、5、6格的连续三个棋子，若第1、2、3格上无

7、棋子而第7、8、9格上均有棋子的话，则可以通过图(b)的操作将这三个棋子移去。我们称4、5、6三颗棋子为模块1。963852741图(a)图(b)模块1算法分析但是经过一些尝试后，我们发现只使用模块1对m×n的真棋盘进行分割效果并不理想。原因在于模块1每次对连续3行同时进行处理，当m不是3的倍数时，分割后总会留下剩余部分。（必须注意的是，图中用蓝框框起来的部分，必须等到其左边的棋子被去除后，才能成为模块1。）剩余部分因此，我们需要对剩余部分进行处理。我们发现，当m不为3的倍数时，总是留下1行或2行剩余部分。由于1行棋子很

8、难去除，当只留下1行时，因为m≥2，且m模3余1，故m至少为4。于是我们就将最上方4行都作为剩余部分，对于剩下的m-4行，由于m-4是3的倍数，这m-4行可以用模块1进行分割。而4行棋子又可分为两部分，每部分都是2行棋子。因此，处理2行棋子的情况就成了关键问题。算法分析经过尝试，我们发现对于图中第2、3、5、6、8、