百度之星2010程序设计大赛 决赛试题

百度爱好者（Baiduer.com.cn）消息，百度之星2010程序设计大赛决赛7月27日早9点30分在百度大厦五福降中天会议室鸣锣开战。百度爱好者给大家带了决赛题目，供有兴趣的朋友研究。试题以“僵尸大战植物”为主题。

题目描述

这是植物大战僵尸里面的一款小游戏《我是僵尸》endless模式，根据植物布局，我们合理的安排僵尸攻击植物，直到吃光每行最左边的大脑。每派出一个僵尸，将会花费你的太阳（购买僵尸的货币），我们目标是就是用最少的太阳通过给定的一组关卡。

题目简化和细节说明

植物的脸都朝右，僵尸脸都朝左，僵尸是从最右面攻过来的；

僵尸不是慢悠悠走的，而是一次走一格或者两格；

僵尸前面有植物， 必须吃完植物后才能前进，除非植物被梯子僵尸架了个梯子；

僵尸跟植物（大脑）在同个格子的时候，僵尸才可以吃植物（大脑）；

大脑的血量为1， 僵尸咬一口就吃掉。吃完大脑后，僵尸消失；

地图上布满了植物（没有空位），僵尸从地图最右边开始攻击；

一个僵尸只会攻击同行的植物，而且永远在这一行上；

没有特殊说明，植物的攻击都只对同一行上的僵尸有效；

有些植物会攻击旁边行的僵尸，如磁铁蘑菇（请参考磁铁蘑菇的说明）；

有些植物会受到旁边行的僵尸影响，比如胆小蘑菇（请参考胆小蘑菇的说明）；

铁桶僵尸，橄榄球僵尸和梯子僵尸在被植物攻击的时候由铁桶，铁帽子，梯子先承受攻击，最后才轮到僵尸本体承受攻击。如果周围有磁铁蘑菇，这三样都会被磁铁蘑菇吸走，被吸走后就是本体直接被攻击。吸走后的铁器将消失；

植物选中一格攻击，发现该格有很多僵尸，而自己只能攻击一个，没有特殊说明，选择先放入的僵尸。如果这些僵尸是同一时刻放入的，选择先出现在输入文件的僵尸。

模拟器细节

我们模拟器分，植物，僵尸，子弹来设计。植物攻击僵尸有几种方式

1、直接攻击僵尸，比如窝瓜，地雷，食人花，磁铁蘑菇等，这种靠自身能力攻击僵尸，在攻击的瞬间就会对僵尸造成伤害。

2、选择发射子弹，发射子弹的行为是不会让僵尸立即扣血，而是等到判断子弹是否能够打击到僵尸时，才会扣僵尸的血。

我们的模拟器将地图变成一个Array[Row][Col]的矩阵，僵尸的行走速度是1/s或者2/s只会从Array[Row][i]走到Array[Row][i-1]或者Array[Row][i-2]。速度为2的僵尸，如果前面有植物挡住，只会前进一格；同理子弹的也是一样。

其它模拟细节

1、这个游戏每1 秒检测一次, 生成该帧的状态图，然后开始判断；

2、每帧的状态生成之后，判断伤害顺序为；

1、检查每个僵尸吃植物（大脑）；

2、检查每个植物是否要攻击僵尸（直接攻击，或者发射炮弹）；

3、检查每枚炮弹是否打击到僵尸；

3、僵尸吃植物，植物死亡时，将立即从植物列表删除；同理炮弹打到僵尸，或者僵尸死亡，也都会立即从对应的链表中删除。极端例子：当植物和僵尸都只剩一滴血的时候，由于僵尸先咬植物，所以植物死了，僵尸不被攻击；

4、植物发射炮弹的时候，炮弹的起始位置为植物所在位置，下一秒开始移动。

植物数据

植物的伤害，攻击性弹药碰到僵尸后都造成1的伤害。

僵尸数据

僵尸吃植物每秒2格血。

程序输入输出

现在假设我们每个游戏场景都是在ROW*COL的方格中满植物，僵尸只能放置在最右面一列的方格中，并发起进攻。地图上放满植物每个方格中的可以同时存在多个僵尸。

输入：

输入由标准输入给出

第一行为1个整数M（0<M<100000000），第一个表示下面这些关卡你总共只能用M的太阳；

第二行也是1个整数N（0<N<100000），表示下面有N个case；

第三行开始为N个case的具体信息，每个case第一行为2个整数Row，Col其中Row表示多少行，Col表示多少列（1<=Row<=10000， 1<=Col<=10000）接下来一共跟着Row行，并用代号标识每行的植物类型， 并且用空格隔开。

输出：

结果需要输出到标准输出

对于每个关卡，第一行为一个整数K，表示本关使用的僵尸数，接下来k行表示每个僵尸的布局，每行有3单词来表示一个僵尸的信息， 以空格隔开，分别表示 僵尸代号（ID）， 行（r）， 时间（time）。它们表示在时间time的时候把一个僵尸放到第r行的最右边上. 对于放置时间相同的僵尸，植物攻击顺序和输出中的顺序一致的。

时间是整数，从0开始计算。我们要求输出的行按僵尸先后放置的时间，顺序一致。

如果你无法解出本关，又不想浪费太阳，请输出1行0；

如果你输出了僵尸，那么即使这个僵尸是过关之后放置的，都要计算它的花费。

在桌面上有一个模拟器，填上你的输入输出文件它可以帮忙计算出你总的花费。

评判标准

我们评判程序会运行多个输入， 然后我们会统计你的解决方案购买僵尸的总开销。

1、通过关卡最多的获胜；

2、关卡数一样， 根据开销由小到大进行排序，决定谁获胜。

如果花费购买僵尸的开销相同，那么会以总的游戏的运行时间为标准，游戏运行总时间少的程序获胜，每关游戏运行时间指顺利过关的时间而不是程序执行时间。

注意事项

1、如果僵尸放置的位置不在地图上，那这个僵尸会被认为无效的，同时相应的花费依然会被扣除；

2、如果僵尸的代号错误（注意大小写和连字符），那么这个僵尸会被认为是非法的，不进行任何操作， 同时会按照最贵的橄榄球僵尸扣除175；

3、如果程序出现异常情况或者程序本身没有完成全部的关卡， 那么排名的时候会以通过的关卡数为准；

4、如果在某一关植物已经全部被消灭，但是还有僵尸被放置到地图上，这些僵尸的花费依然会被计算；

5、如果花费的太阳数超过数据的给定值， 模拟器在放置僵尸花费超过现在太阳数的时候结束游戏，以此时的结果作为最后结果。

【Sample Input】

100000

3

5 1

Potato-Mine

Potato-Mine

Potato-Mine

Potato-Mine

Potato-Mine

5 2

Potato-Mine Potato-Mine

Potato-Mine Potato-Mine

Potato-Mine Potato-Mine

Potato-Mine Potato-Mine

Potato-Mine Potato-Mine

5 2

Peashooter Wall-Nut

Peashooter Wall-Nut

Peashooter Wall-Nut

Peashooter Wall-Nut

Peashooter Wall-Nut

【Sample Output】

5

Pole 0 0

Pole 1 0

Pole 2 0

Pole 3 0

Pole 4 0

10

Imp 0 0

Imp 1 0

Imp 2 0

Imp 3 0

Imp 4 0

Pole 0 1

Pole 1 1

Pole 2 1

Pole 3 1

Pole 4 1

5

Pole 0 0

Pole 1 0

Pole 2 0

Pole 3 0

Pole 4 0

输入输出说明

第一关：每列都是土豆雷，我们都用撑杆跳的过去。如果你派小僵尸过去，那么僵尸会全砸死，虽然植物也全被消灭了，但是你还是没过关，还需要派小僵尸，花费更多。