TopCoder Marathon Match 4

题目改编自己经典游戏Battleship,原版的游戏是给出一个n*m的方格阵,里面有k条船,每条船的宽度都是1但长度不一,方向要么横着(纵坐标相同)要么竖着(横坐标相同),玩家每回合选择一个点丢炸弹,系统返回炸到与否。这道题目改了一些条件:给出一个n*n的方格阵,每次可以丢x个炸弹,系统返回炸到了哪些船和每条船炸到几个点,但不告之是哪些炸弹炸到的。要求程序在尽可能短的回合内,炸完所有的船。

看到题目,最初的想法是完全随机投点,这样做的好处是:1、使自己有个分数先,0分太难看了;2、这个算法保证能在规定时间内结束,可以用来测试程序的完整性和对题目理解的正确性。迅速写完之后提交,出乎意料拿了30多分(满分100),看来完全随机的效率还不错。

然后开始改进程序,虽然系统不返回哪个炸弹炸到了船,但是只要有船被炸到,那一回合的炸弹附近必然有船,下一回合就先炸那附近的点。这么一改,得分反而下降了,郁闷=.=,分析原因,可能是下一回合选取点的优先顺序问题,因为有多种情况可以估算可能有船的点,不同的if顺序就会导致程序效率的明显差别,于是继续改。

再然后就想到了给每个点都设一个可能度的值,每一轮炸完之后,都对相应的点的可能度进行评估,然后选出可能度最高的几个点进入下一轮。评估的条件有,如果一个点炸到了船,则它周围的四个点可能度提升;如果两个点炸到了船并且它们在一条直线上距离小于那条船的长度,则它们所在直线上相应点的可能度提升;如果一个点没有炸到船,则它周围点的可能度下降(这一条有争议,多次试验下来效果不好)。这样一改,分数一下子上到了50多分,效果非常好。

但是最高分有90多分,怎样继续优化是一个问题。这时我的程序已经分为2部分,一部分是初始化时,点的顺序,因为最初的几回合,可以获得的信息比较少,但这几回合非常关键,怎么安排最初炸的点是要好好考虑的;另一部分是怎样利用已知信息,计算点的可能度。这2部分的优化都很伤脑筋,而我的分数一直在50分左右徘徊,很郁闷。


发表评论

电子邮件地址不会被公开。 必填项已用*标注