挖洞

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 $的最小值?