构造最难聚合的板块

KeyTo9_Fans

在n*n的方格阵里放置一些方块■，其余地方为空地。

把一个方块■向上、下、左、右移动到与它相邻的空地称为一步。

把所有方块以四连通的形式连在一起称为聚合。

聚合这些方块所需的最少移动步数称为聚合难度。

问：

如何放置这些方块■，使得聚合难度最大？

建议从n=1开始做，能做多大算多大。

/*

如果觉得上面的描述不够清楚，可以在这里

http://tieba.baidu.com/f?kz=664200910

阅读具体细节。

*/

〇〇

这种游戏在数学那个子学科

KeyTo9_Fans

大概是算法设计与分析方面的吧。

如果要归类的话，我承认这不太属于数学类问题，应该归为计算机类比较好。

但是我希望能从这些问题的结果中找出一些规律，然后用数学方法证明它。

这才是我要研究这些问题的最终目的。

jiaon

直观的感觉是尽量把这些方块均匀的分到方格里聚合难度最大

mathe

应该是尽量放在4个角上。只是每个角上的数目需要研究一下

mathe

比如n=4可以做到8步，如
■□□■
□□□□
□□□□
■□□■
以及
■■■■
□□□□
□□□□
■■■■
都是8步

mathe

我们如果先考虑对于较大的2n边形。考虑一个特殊的初始状态：4个角上都有d*d个黑方块，其它地方都没有。
那么如果最后将所有方块合并成一个2d*2d的大方块，需要移动$4d^2*2(n-d)$,这个表达式在d=2n/3的时候取到最大值。我估计这个方案很可能就是最好的方案了，而2n/3不是整数时分别检查上取整和下取整两个结果。
同样对于奇数边也应该有类似的结果。

mathe

错了，最终结果是不需要合并成大方块的

jiaon

■■■■
□□□□
□□□□
■■■■
不用8步，6步就可以
■■■■
□□■□
□□■□
□■■□

KeyTo9_Fans

■■■■
□□□□
□□□□
■■■■

只需4步:

□■■■
□■□□
□■□□
□■■■

目前发现n=3到n=5都是直接在四个角各放一个方块就可以了，步数为4(n-2)。

但n=5有并列的最优解，同为12步:

■■□□■
□□□□■
□□□□□
■□□□□
■□□■■

而且聚合难度似乎不是线性增长的，应该是平方级的。

所以估计4(n-2)的形式会在n=6的时候被打破，升级为O(n^2)的级别。