挖洞

northwolves

使用单元格正方形拼成内部含有n个孔的矩形,至少需要多少个正方形? 比如n=4时,需要21个 n=5时,需要20个 ■■■■■ ■ ■ ■ ■■ ■■ ■ ■ ■ ■■■■■

northwolves

n=4 n=5

KeyTo9_Fans

楼主是否对我们隐瞒了一些限制条件？ 例如： 如果外围边框一定要是完整的矩形，则这样摆： n=4用20个 n=5用20个 如果外围边框要完整，但不一定是矩形，则这样摆： n=4用18个 n=5用20个 如果外围不要求完整，但所有方块必须四连通，则这样摆： n=4用17个 n=5用19个 如果既不要求外围完整，也不要求连通，则这样摆： n=4用9个 n=5用11个 楼主的本意应该是哪一种限制条件呢？

northwolves

似乎 n=6 时,H(6)=24 n=7时,H(7)=28 N=8时,H(8)=27

gxqcn

3# KeyTo9_Fans 看题意，及结合作者的示例图， 似乎是要求：在一个大的矩形框中抠出n个洞，要求它们不连通（是指“上下左右”四边不联通，但四顶点可连通）。 在指定n的情况下，求该矩形最小面积及对应布局。

KeyTo9_Fans

那我3楼的第一幅图n=4用20个不是比楼主的21个更好吗？ 为什么楼主不用20个，而要用21个？

mathe

应该是楼主弄错了。

mathe

对于m*n的矩形，里面最多只能有$[((m-2)(n-2)+1)/2]$个洞。 然后就容易计算了

northwolves

3# KeyTo9_Fans 看题意，及结合作者的示例图， 似乎是要求：在一个大的矩形框中抠出n个洞，要求它们不连通（是指“上下左右”四边不联通，但四顶点可连通）。 在指定n的情况下，求该矩形最小面积及对应布局。 gxqcn 发表于 2009-11-24 07:41

对,就是这个意思

northwolves

对于m*n的矩形，里面最多只能有$[((m-2)(n-2)+1)/2]$个洞。 然后就容易计算了 mathe 发表于 2009-11-24 09:13

你的意思是说,需要求得: 满足条件$[((m-2)(n-2)+1)/2]$=n 的$(m-1)*n $的最小值?