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

2006年全国信息学冬令营讲座棋盘中的棋盘——浅谈棋盘的分割思想复旦大学附属中学俞鑫【摘要】现在的信息学竞赛题目，经常以某种数学模型作为出题媒介，使题目充满乐趣性和深厚的数学底蕴，而棋盘就是其中一种重要的数学模型。本文着重对棋盘的一种重要思想——棋盘的分割思想进行分析，并引入两道典型例题，说明棋盘分割应遵循的规律，使读者能对纷繁复杂的棋盘分割有一定的了解。【关键词】数学模型棋盘算法思想【正文】引言信息学是一门综合性的学科，也是一门充满乐趣的学科。棋盘，作为一个重要的数学模型，以其趣味性和复杂的数学特性经常受到出题者的青睐。因此，深入研究棋盘中蕴含的算法思想对于一名信息学爱好者而言是十分必要的。在此，我将着重说明棋盘中的一种重要思想——棋盘的分割思想。2006年全国信息学冬令营讲座对于一个m×n的棋盘，它所含的子棋盘共有Cm×Cn个，而其分割方法更是不计其数。巧妙地对棋盘进行分割，可以解决许多种类的棋盘问题。例一：棋盘覆盖（经典问题）题目描述：在一个2k×2k方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有4k种情形。因而对任何k≥0，有4k种不同的特殊棋盘。图中的特殊棋盘是当k=2时16个特殊棋盘中的一个。子棋盘3子棋盘2子棋盘12006年全国信息学冬令营讲座在棋盘覆盖问题中，我们要用以下4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。易知，在任何一个2k×2k的棋盘覆盖中，用道的L型骨牌个数恰为(4k-1)/3。现求一种覆盖方法。输入：第一行为k（棋盘的尺寸），第二行为x,y(1≤x,y≤2k)，分别表示特殊方格所在行与列。输出：共2k行，每行2k个数，分别表示覆盖该格的L型的编号（特殊格用0表示）。样例：输入：212输出：102211324种不同形态的L型骨牌2006年全国信息学冬令营讲座43354455算法分析由棋盘尺寸为2k×2k，我们可以想到将其分割成四个尺寸为2k-1×2k-1的子棋盘可是，由于含特殊方格的子棋盘与其它子棋盘不同，问题还是没有解决。只要稍作思考，我们就可以发现，只要将L型如图放置在棋盘的中央，就可以使四个子棋盘都变成特殊棋盘。此时问题也变成了四个相同的子问题，只需运用简单的递归就可以解决这道问题了。2006年全国信息学冬令营讲座二位数组num:覆盖该格的L型的编号，下文所说的对方格赋值即对其对应的num赋值。x1,y1:当前棋盘左上角方格的行号与列号x2,y2:当前棋盘右下角方格的行号与列号x3,y3:当前棋盘中特殊格的行号与列号ck:当前棋盘的尺寸（2ck×2ck）cnum:当前L型骨牌的编号初始值：开始时，将num[x,y]设为0当ck=0时：棋盘尺寸为1×1，该格为已赋值的特殊格，不进行任何操作。当ck0时：设xm为(x1+x2+1)/2，ym为(y1+y2+1)/2，比较x3与xm，y3与ym的大小就能知道特殊格所在子棋盘的位置，将另外三个子棋盘中靠近棋盘中央的三个方格赋值为cnum，kck1yx2k2k11cnumy3x3y2x2y1x1xmymx1x2y1y22006年全国信息学冬令营讲座并分别作为这三个子棋盘的特殊格。随后cnum增加1。再对这四个棋盘分别进行递归处理。复杂度分析时间复杂度：O(4k)空间复杂度：O(4k)由于覆盖一个2k×2k棋盘所需的L型骨牌个数为(4k–1)/3，故该算法是一个在渐进意义下最优的算法。参考程序GAMERS.PAS小结将棋盘分割成子棋盘，要遵循以下两点：1.分割出的棋盘要与原棋盘尽可能相像。2.将原棋盘分割后尽量不要留下剩余部分。但如果分割后必定留下剩余部分又该如何呢？下面这道例题就是用来解答这个问题的。2006年全国信息学冬令营讲座例二：孔明棋问题（URAL1051）题目描述：在一个无限大的棋盘的节点上有一些棋子，这些棋子构成一个m×n的矩形(m为高度，n为宽度且1≤m,n≤1000)。你可以用一个棋子跳过另一个相邻的棋子，被跳过的棋子将被移去，请你求出最少能剩下几个棋子。输入：m,n输出：最少能剩下的棋子数样例：输入：34输出：2下面是一种走法：一种移动方法2006年全国信息学冬令营讲座2006年全国信息学冬令营讲座2006年全国信息学冬令营讲座算法分析由于m=1或n=1的情况比较特殊，我们先处理m,n≥2的情况。为了叙述方便，我们称由棋子所在格子组成的棋盘为“真棋盘”。通过样例，我们可以发现，对于图(a)中位于4、5、6格的连续三个棋子，若第1、2、3格上无棋子而第7、8、9格上均有棋子的话，则可以通过图(b)的操作将这三个棋子移去。我们称4、5、6三颗棋子为模块1。图(b)963852741图(a)模块12006年全国信息学冬令营讲座但是经过一些尝试后，我们发现只使用模块1对m×n的真棋盘进行分割效果并不理想。原因在于模块1每次对连续3行同时进行处理，当m不是3的倍数时，分割后总会留下剩余部分。（必须注意的是，图中用蓝框框起来的部分，必须等到其左边的棋子被去除后，才能成为模块1。）因此，我们需要对剩余部分进行处理。我们发现，当m不为3的倍数时，总是留下1行或2行剩余部分。由于1行棋子很难去除，当只留下1行时，因为m≥2，且m模3余1，故m至少为4。于是我们就将最上方4行都作为剩余部分，对于剩下的m-4行，由于m-4是3的倍数，这m-4行可以用模块1进行分割。而4行棋子又可分为两部分，每部分都是2行棋子。因此，处理2行棋子的情况就成了关键问题。剩余部分2006年全国信息学冬令营讲座经过尝试，我们发现对于图中第2、3、5、6、8、9格上的六个棋子，若第1、4、7格无棋子且第11、12格上有棋子的话，则可通过一系列的操作将这六颗棋子去除。我们称这六颗棋子为模块2。具体操作如下：987126311521041模块22006年全国信息学冬令营讲座有了模块1和模块2这两样工具，对m×n真棋盘的分割就得心应手了。对任意的m×n的真棋盘，当n≥5时，对于棋盘中最左边的3列棋子形成的m×3的棋盘，我们通过下面的操作将其去除。1、当m是3的倍数时首先将左边3列分成m/3个3×3的子棋盘。再将每个3×3的子棋盘分成3个3×1的子棋盘。每次对最上方最左边的3×1棋盘进行操作，由于其左方无棋子，可以保证它是模块1，将其去除。2、当m模3余1时由于m≥2，故m至少是4，m×3棋盘最上方的2×3子棋盘是一个模块2，将其去除。(m-2)×3棋盘最上方的2×3子棋盘也是一个模块2，将其去除。对于剩下的(m-4)×3棋盘，由于m-4是3的倍数，同1进行操作，将其去除。2006年全国信息学冬令营讲座3、当m模3余2时m×3棋盘最上方的2×3子棋盘是一个模块2，将其去除。对于剩下的(m-2)×3棋盘，由于m-2是3的倍数，同1进行操作，将其去除。设m与p关于3同余，n与q关于3同余(2≤p,q≤4)，对于任意的m×n的真棋盘，当n≥5时，不断通过上述操作除去最左边3行，真棋盘规模将发生如下变化：m×nm×(n-3)m×(n-6)…m×q再将棋盘顺时针旋转90度，真棋盘规模变为q×m，继续进行上述操作：q×mq×(m-3)q×(m-6)…q×p再将棋盘顺时针旋转90度，真棋盘规模变为p×q。现在，我们只要对p×q的真棋盘进行操作，便可得到m×n的真棋盘经过操作最少能得到的棋子数的上界。下面是对p、q各种可能情况的讨论：①p=2,q=22006年全国信息学冬令营讲座剩下1颗棋子②p=2,q=3剩下2颗棋子③p=2,q=4黄框中的6颗棋子构成模块2，将其一起去除。剩下1颗棋子④p=3,q=2将棋盘顺时针旋转90度后，与p=2,q=3的情况相同。剩下2颗棋子⑤p=3,q=32006年全国信息学冬令营讲座蓝框中的3颗棋子构成模块1，将其一起去除。剩下2颗棋子⑥p=3,q=4由样例的操作知，剩下2颗棋子。⑦p=4,q=2将棋盘顺时针旋转90度后，与p=2,q=4的情况相同。剩下1颗棋子⑧p=4,q=3将棋盘顺时针旋转90度后，与p=3,q=4的情况相同。剩下2颗棋子⑨p=4,q=4黄框中的6颗棋子构成模块2，将其一起去除。2006年全国信息学冬令营讲座剩下1颗棋子由于当m模3余0、1、2时，p分别为3、4、2。而当n模3余0、1、2时，q分别为3、4、2。我们可以列出下面这张表格来表示对各种情况的m、n，m×n的真棋盘经过操作最少能得到的棋子数的上界。为了叙述方便，我们设m×n的真棋盘经过操作最少剩下s颗棋子。经过观察可以发现，当m、n中有1个数是3的倍数时，s的上界为2，否则为1。现在，我们只需要证明，这个上界就是答案。⑴对任意的正整数m、n，显然，s≥0。若s=0，由于每次操作恰减少一112211212220210mmod3nmod32006年全国信息学冬令营讲座颗棋子，所以最后一次操作前恰好剩余1颗棋子，但对于1颗棋子无论如何都不可能进行操作，矛盾。所以s≥1。⑵当m、n中有一个数是3的倍数时，不妨设m是3的倍数（否则将棋盘顺时针旋转90度，即为m是3的倍数的情况），下面我们证明s≥2。首先，我们对无限大的棋盘进行三色间隔染色。其中，无论横排还是竖排的任意3个连续方格，必为一红、一蓝、一白。对于m×n的真棋盘中的任何一列，都是一个m×1的子棋盘，而每一个m×1的子棋盘又可以分成m/3个3×1的子棋盘。于是，m×n的真棋盘可以分为若干个3×1的子棋盘，而每个3×1的子棋盘中都有红、白、蓝方格各一个，所以，真棋盘中红、白、蓝方格的数目相同。设在红、白、蓝格上的棋子数分别为a、b、c，开始时a=b=c。对于每一次操作，都可以看作连续3个格中，两个格中的棋子被拿去，而另一格上多了一颗棋子，于是a、b、c中有两个数减1，另一个数加1，奇偶性都发生了变化，所以a、b、c始终同奇同偶。若s=1，由于操作完成之后，s=a+b+c，故a、b、c中两个为0，一个为1，奇偶性不同，矛盾。又因为s≥1，所以s≥2。2006年全国信息学冬令营讲座通过上面的证明，我们得出了s的下界，它与先前的上界完全相同。于是，当m,n≥2时，若m、n中有一个数是3的倍数，则s=2；否则，s=1。对于m=1的情况，我们同样先通过一个例子给出上界。由于当m=1时，n颗棋子排成一行，于是可以将它们从左向右分别标号为1、2、3……n。设k=[n/2]，因为2×k≤n，我们对这n颗棋子进行k次操作。第i次操作(1≤i≤k)为将标号为2×i的棋子跳过标号为2×i-1的棋子。由于在第i次操作之前，在标号为2×i-1的棋子左边的棋子不是被去除，就是向左移动，而其它棋子并未移动，于是标号为2×i-1的棋子的左边一格上无棋子，所以操作是合理的。经过k次操作，棋盘上剩余n-[n/2]颗棋子，这就是最少剩余棋子数的上界。下面只需证明n-[n/2]是最少剩余棋子数的下界即可。首先，一旦在某次操作后，不再有未经操作的棋子，则在以后的操作中也不会再次出现未经操作的棋子，若存在这样的操作，我们就称这次操作为关键操作。于是，有未经操作棋子的阶段为从开始到关键操作或无法操作前。为了证明原问题，我们必须证明两个引理①未经操作的棋子总是排成连续一行。②在未经操作棋子左边的任两颗已操作棋子不相邻，且未经操作棋子中最左边一颗棋子的左边两格为空格。321n……2006年全国信息学冬令营讲座③在未经操作棋子右边的任两颗已操作棋子不相邻，且未经操作棋子中最右边一颗棋子的右边两格为空格。引理1：若一个棋盘中棋子的分布同时满足条件①②③，则下一步进行操作的两颗棋子必然是两颗未经操作的棋子。引理1的证明：若一个棋盘满足这三个条件，则对于在未经操作棋子左边的任何一颗已操作棋子m，它的两侧不是在未经操作棋子左边的已操作棋子，就是未经操作的棋子中最左边的一颗棋子，而根据条件②，它们所在格子与棋子m所在格子间至少有一个空格，于是对m无法进行操作。同理，对于在未经操作棋子右边的任何一颗已操作棋子n也无法进行操作。于是，下一步