求教一个问题

给出一个10x10的矩形网格场地，在这块场地上尽可能多地用1x1的方形（建筑物）进行填充。这些方形至少要与一个空置的单元相邻，所有这些空置的单元必须是连通的。

       这个问题反映了在矩形场地上放置建筑物的问题，在确保每个建筑物单元都是可以通过道路到达的情况下（也可以看作形成连通的院落），保证最高的建筑密度。

[img]http://dx.xycq.net/photo/albums/userpics/10010/123~3.jpg[/img]

上图是10x10的情况下的三种最优方案 最多可以放置[color=Blue]61[/color]个建筑单元 我把这个问题推广到mxn做了一下

if(m>n){
  swap(m,n);
}
//如果m>n则交换m,n的值

k=m div 3;l=m mod 3;sky=(n mod 3)*l;
//整除 取余 乘积

switch(sky){
case 1:A=1;
case 2:A=2;
case 4:A=3;
}
//1x1--A=1;1x2--A=2;2x2--A=3;

min=n+(m+n-3*k+2)(k-1)+((n-3(k-1)) div 3)*(l+1)+A;
//这个是满足条件的最小的道路网长度

这个是我用旋转放置的方法得到的yy公式，我感觉是对的，也没发现什么问题，但是我不会证明，也没想到更简单的表达方式，各位达人能不能推导一下（或者纠正我的错误），下面还要想枚举出各种可能情况的算法，目前打算用上面那个做启发函数作图形覆盖，或者用遗传算法生成，头痛，大家有空就提提思路吧:Th

[[i] 本帖最后由 青木风亮 于 2007-5-17 19:48 编辑 [/i]]

可以在 m x n 上做一个 random tree，然后挑出元素最多的。