棋盘中的棋盘—浅谈棋盘的分割思想

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

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

2、研究棋盘中蕴含的算法思想对于一名信息学爱好者而言是十分必要的。在此，我将着重说明棋盘屮的…种重要思想一一棋盘的分割思想。对于一个mXn的棋盘，它所含的子棋盘共有CmXCn个，而其分割方法更是不计其数。巧妙地对棋盘进行分割,可以解决许多种类的棋盘问题。子棋盘2ir///J子棋盘3例一；棋盘覆盖（證與问軀丿题目描述:在一个2kX2k方格组成的棋盘中，若恰有一个方格与其他方格不在棋盘覆盖问题中，我们要用以下4种不同形态的L型骨牌覆盖同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘。显然特殊-个给定的特殊棋盘

3、上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。易知，在任何一个2kX2k的棋盘覆盖中，用道的L型骨牌个数恰为（43）/3。现求一种覆盖方法。4种不同形态的L型骨牌输入：笫一行为k（棋盘的尺寸），第二行为x,y（1Wx,yW2^,分别表示特殊方格所在行与列。输出：共2玄行，每行2玄个数，分别表示覆盖该格的L型的编号（特殊格用0表示）。样例：输入：212输出：43354455由棋盘尺寸为2kX2k,我们可以想到将其分割成四个尺寸为21X21的子棋盘是，由于含特殊方格的了棋盘与其它了棋盘不同，问

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

5、k2kXVk1开始时，将num[x,y]设为0当ck=O时：棋盘尺寸为1X1,该格为已赋值的特殊格，不进行任何操作。当ck>0时：设xm为(x1+x2+1)/2,ym为(y1+y2+1)/2,比较x3与xm,y3与ym的大小就能知道特殊格所在子棋盘的位置，将另外产个子棋盘中靠近棋盘中央的•个方格赋值为cnum,y1ymy2x1xmx2并分别作为这三个了棋盘的特殊格。随后cnum增加1。再对这四个棋盘分别进行递归处理。时间复杂度：0(4k)空间复杂度:0(4/()由于覆盖一个2gk棋盘所需的L型骨牌个数为

6、(4/<-1)/3,故该算法是一个在渐进意义下最优的算法。GAMERS.PAS小住将棋盘分割成子棋盘，要遵循以下两点：1•分割出的棋盘要与原棋盘尽可能相像。2.将原棋盘分割后尽量不耍留下剩余部分。但如果分割后必定留下剩余部分又该如何呢？下面这道例题就是用来解答这个问题的。例二,，孔朗棋问龜（宠衣么％勺丿题口描述：在一个无限大的棋盘的节点上有一些棋子，这些棋子构成一个mXn的矩形（m为高度，n为宽度J11WmjWIOOO）。你可以用一个棋子跳过另-个相邻的棋子，被跳过的棋子将被移去，请你求出最少能剩下几个

7、棋子。□一种移动方法输入：m,n输出：最少能剩下的棋子数样例：输入：34输出：2下而是一种走法:1B□□•r••••••♦Hx••••••7■•■■■■r>r•■>•^■1□a□■□□□I3□□■i■E0B■□□由于或n=1的情况比较特殊，我们先处理m,n^2的情况。为了叙述方便，我们称由棋子所在格子组成的棋盘为“真棋盘”。通过样例，我们可以发现，对于图(a)中位于4、5、6格的连续三个棋子,若第1、2、3格上无棋了而第7、8、9格上均有棋子的话，则可以通过图(b)的操作将这三个棋子移去。我们称4、5、

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