Topcoder Marathon 11

Marathon的System Test也是Marathon式的，等了好久。

最后的Rank终于出来了，Rank 8, Score 388.10, Rating 1565。
第一名好夸张，有好多Case都是超我一倍的呀！赞~

第一次做Marathon，这次的题目是贪吃蛇，郁闷...是比较没新意的题目...个人感觉贪吃蛇运气因素较大（测试数据多的话，当然可以降低偶然性），没有觉得能在每盘上都赢得最高分的算法，但确实应该有能保证在大多数情况下表现出色的算法。
我的算法可以说是偶然性十足 -_-b，我也很纳闷，但就是没法解释，所以只能说偶然。Example Test 15次，Submittion 4次， Submittion的成绩是 30.76 -> 28.44 -> 28.13 -> 27.43 一个比一个差 -_-b （但我的想法好象是一个比一个周密才对呀）。

我的算法的思路是这样的：

Step 1. 将Snake的一次行为（调用 moveSnake()）划分为三个小算法， 即计算路径、选路径、移动。

Step 2. 初始化地图我不算在算法里，因为太简单了。计算路径是指，用搜索类的算法，搜索出从Snake到Food的可能路径。

在这一步，我起初使用的是最简单的bfs（就是我得分最高的时候 -_-b）。优点是找到的豆路径最短，缺点是Snake老是擦豆而过，因为路径只关心最短的问题，如果路径上没有经过某个豆，那么即使该豆可以顺便吃掉，Snake也会置之不理。
然后，我改进了算法，使用pfs，以吃到的豆的个数为优先级别进行路径搜索。这样每次都是从吃豆最多的路径继续往下搜，就可以保证将顺路的豆子都能吃掉。结果是，这个pfs每次比bfs走的步数要少，从虚拟程序上看，Snake聪明了许多，但就是吃豆数不见长。

我这有一个我没去实现的算法（因为后面两天都有事），想法是使用多端bfs：Snake头和各个Food各准备一个队列，然后每个循环，依次对每个队列进行扩展。当某个Food队列扩展的路径碰到了Snake的路径，那么Snake到该Food有路；若是Food队列碰到Food队列，那么这两个Food有路。且所有路径最短。改算法的好处是能求出所有最短路径、而复杂度与bfs相同，只是实现有点复杂。

Step 3.选路径，在我自己测试的时候发觉，选路径对于整体结果影响最大！也可以说是偶然性最大的一块。依据Step2中的bfs或者pfs所得到的结果，应该说Snake到Food的路径是固定的，所以就可以说是选下一个受吃的Food。怎么选Food呢？
我给每个Food设置了三个值：

1. 吃到该Food的路径上顺便可以吃到的Food
2. 假设Snake吃该Food，那么吃到Food后，Snake的可移动空间，即一次bfs从Food点开始计算空间（要先模拟好Snake吃到Food的位置）。
3. 该区域内还有多少未吃的Food，即如果Snake逃不出该Area，可能还有多少Food可以吃。

综合上述三点，可以计算出一个优先级。我以Area大小和Snake蛇身长度为主要依据，若蛇身长远远超过Area那么Snake应该说可以有更大的活动，也可以说Snake有机会逃出该Area。再依据Snake吃该Food时顺便吃的Food和该Area潜在的Food同样影响这个优先度。若优先度相似，则可能再吃的Food数量加上顺便吃的Food数量为第二优先级。
在这里，Area的关系十分重要，很明显的，因为Area表示Snake存活概率高，只要活着就不怕没Food吃。
比如下面两个情况：

 #                   ###
#O                  #  #
 #                   #O#

很明显，这些Food是DeathFood，优先级要最低，也就是说实在没Food可吃才吃他们。

对于多端bfs，选择的就不是Food了，而是真正的Path。这个就可能和前面的算法完全不同了，我又没实现多端bfs，而且这个貌似更加复杂，就没深入。。。另一方面是被偶然性搞怕了，深怕花了大半天写的程序结果还不如以前的好。

Step 4.移动，即与平台交互，这个只要认真看看平台文档就行了。另外，为了保持Snake和Food位置与平台同步，自己也要模拟Snake的移动。

附加一个想法，由于Step3提到，Snake吃到Food后的Area问题。所以我考虑是否可以通过预广搜一次，标记所有的Area（或者这里称Prison，也就是整个Area有一个格子负责与外界连着，其他格子均与非此Area的格子无连接）。起算法是，由任意一点，开始bfs，但搜索到的格子只有一个目（类似于围棋的目，就是下面这种情况，X是搜索过的格子，#是障碍物，@就是只有一个目）：

XX#
XX@
XX#

这种情况下，将@放入一个Door队列（初始为空）。若搜索第二次遇到@，则@不是Door，标记为搜索过的格子。在待搜索队列为空时，若Door个数大于1，则Area不是Prison，可以再扩展；否则该Area为Prison，同时去除该Door。然后任取一个外面一个没有搜索过的格子再bfs，同样，若搜索到某个Door则取消它Door的资格，否则搜索完再计算Door个数。
可能出现这种情况： Prison - Door - 2个Door的Area - Door ，此时，2个Door的Area不是Prison，但它加上里面的Door和Prison就是一个Prison。可以说是有层次关系的。
总之，算法很复杂，当时摆着电脑楞了许久，最后还是决定先暂时把这个想法搁着 -_-b 。