算法合集之《浅谈棋盘的分割思想》

《算法合集之《浅谈棋盘的分割思想》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、棋盘中的棋盘——浅谈棋盘的分割思想复旦大学附属中学俞鑫【摘要】现在的信息学竞赛题目，经常以某种数学模型作为出题媒介，使题目充满乐趣性和深厚的数学底蕴，而棋盘就是其中一种重要的数学模型。本文着重对棋盘的一种重要思想——棋盘的分割思想进行分析，并引入两道典型例题，说明棋盘分割应遵循的规律，使读者能对纷繁复杂的棋盘分割有一定的了解。【关键词】数学模型棋盘算法思想【正文】引言信息学是一门综合性的学科，也是一门充满乐趣的学科。棋盘，作为一个重要的数学模型，以其趣味性和复杂的数学特性经常受到出题者的青睐。因此，深入研究棋盘中蕴

2、含的算法思想对于一名信息学爱好者而言是十分必要的。在此，我将着重说明棋盘中的一种重要思想——棋盘的分割思想。对于一个m×n的棋盘，它所含的子棋盘共有Cm×Cn个，而其分割方法更是不计其数。巧妙地对棋盘进行分割，可以解决许多种类的棋盘问题。子棋盘1子棋盘2子棋盘3例一：棋盘覆盖（经典问题）题目描述：在一个2k×2k方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有4k种情形。因而对任何k≥0，有4k种不同的特殊棋盘。图中的特殊棋盘是当k=2

3、时16个特殊棋盘中的一个。在棋盘覆盖问题中，我们要用以下4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。易知，在任何一个2k×2k的棋盘覆盖中，用道的L型骨牌个数恰为(4k-1)/3。现求一种覆盖方法。4种不同形态的L型骨牌输入：第一行为k（棋盘的尺寸），第二行为x,y(1≤x,y≤2k)，分别表示特殊方格所在行与列。输出：共2k行，每行2k个数，分别表示覆盖该格的L型的编号（特殊格用0表示）。样例：输入：212输出：1022113243354455算法分析由

4、棋盘尺寸为2k×2k，我们可以想到将其分割成四个尺寸为2k-1×2k-1的子棋盘可是，由于含特殊方格的子棋盘与其它子棋盘不同，问题还是没有解决。只要稍作思考，我们就可以发现，只要将L型如图放置在棋盘的中央，就可以使四个子棋盘都变成特殊棋盘。此时问题也变成了四个相同的子问题，只需运用简单的递归就可以解决这道问题了。二位数组num:覆盖该格的L型的编号，下文所说的对方格赋值即对其对应的num赋值。x1,y1:当前棋盘左上角方格的行号与列号x2,y2:当前棋盘右下角方格的行号与列号x3,y3:当前棋盘中特殊格的行号与列号

5、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，比较x3与xm，y3与ym的y1ymy2大小就能知道特殊格x1所在子棋盘的位置，将另外三个子棋盘中靠近棋盘中央的三个xm方格赋值为cnum，x2并分别作为这三个子棋盘的特殊格。随后cnum增加1。再对这四个棋盘分

6、别进行递归处理。复杂度分析时间复杂度：O(4k)空间复杂度：O(4k)由于覆盖一个2k×2k棋盘所需的L型骨牌个数为(4k–1)/3，故该算法是一个在渐进意义下最优的算法。参考程序GAMERS.PAS小结将棋盘分割成子棋盘，要遵循以下两点：1.分割出的棋盘要与原棋盘尽可能相像。2.将原棋盘分割后尽量不要留下剩余部分。但如果分割后必定留下剩余部分又该如何呢？下面这道例题就是用来解答这个问题的。例二：孔明棋问题（URAL1051）题目描述：在一个无限大的棋盘的节点上有一些棋子，这些棋子构成一个m×n的矩形(m为高度，n

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

8、三颗棋子为模块1。147258369模块1图(a)图(b)但是经过一些尝试后，我们发现只使用模块1对m×n的真棋盘进行分割效果并不理想。原因在于模块1每次对连续3行同时进行处理，当m不是3的倍数时，分割后总会留下剩余部分。（必须注意的是，图中用蓝框框起来的部分，必须等到其左边的棋子被去除后，才能成为模块1。）剩余部分因此，我们需要对剩余部分进行处理。我们发现