UC知道一个有趣的算法问题。
来源：百度知道 编辑：UC知道 时间：2024/06/14 12:28:45
帮我想个算法吧：
假设一个m*m的地图，在这个地图上盖大楼。大楼有4种：A类10层，B类20层，C类30层，D类40层。无论ABCD哪类大楼，每层都可以居住10人。A类可以在地图的任意地方建筑，B类大楼的周围（相邻的点，但不包括对角线上的点）必须至少有一个A类大楼，C类大楼的周围必须至少各有一个A类和B类的大楼，D类的周围必须至少各有一个A类、B类和C类的大楼。请问，M×M的地图上，如何建造大楼，使得可以居住的人数最多？
规则例如：
A B C
C D A
B A A
更要命的是,假设你填了2,那么2周围那个1就没用了,如果条件允许,可以被再填成别的数.
假设一个m*m的地图，在这个地图上盖大楼。大楼有4种：A类10层，B类20层，C类30层，D类40层。无论ABCD哪类大楼，每层都可以居住10人。A类可以在地图的任意地方建筑，B类大楼的周围（相邻的点，但不包括对角线上的点）必须至少有一个A类大楼，C类大楼的周围必须至少各有一个A类和B类的大楼，D类的周围必须至少各有一个A类、B类和C类的大楼。请问，M×M的地图上，如何建造大楼，使得可以居住的人数最多？
规则例如：
A B C
C D A
B A A
更要命的是,假设你填了2,那么2周围那个1就没用了,如果条件允许,可以被再填成别的数.
很有趣，讨论一下吧：
先随机放个A，
将它的周围8个位置编号1，2，3，4，5，6，7，8
从1号到8号依次放楼，能放D就放D，不能就放C，C还不能就放B,
然后再以已放好的这九个为中心，放它周围的16个，
按相同的规则编号，然后放楼。
这样继续下去，直到放完。
如果碰到边界，也没关系，把除去边界部分编号处理。
这里有三个不确定的问题：
1、随机放和指定地方放，结果相同吗？
（可以调试测出）
2、先放A和先放B,C,D结果相同吗？
（也可以调试测出）
3、按这个路径扩展结果是不是最好的，还是按其他路径扩展会更好。
（找几条路径试试）
呃……怎么那边删了又贴到这里来了..
等价说法是
在M×M的方格内填上1，2，3，4的数字，并且要求
4周围必须有1，2，3
3周围必须有1，2
2周围必须有1
求使这M×M个格内数字总和最大的填法。
3×3的格有个更好的填法
C A B
B D C
C A A
至于通用算法……艾…………正在寻找中..
列举所有的可能，算出其容量
最大的容量哪个就是你的填法
这不是游戏TowerBloxx嘛..
【◎艾】填法有错
C A B
B D C
C A A
第二行的B没有A相连
这个路径太难了！！！