梵梵最近在玩 PVZ 泳池关卡,不考虑僵尸的移动以及植物的冷却时间,他想知道只运用樱桃炸弹(消耗阳光 150,樱桃炸弹可以消灭以它为中心周围 9 个格子内的僵尸)和荷叶(消耗阳光 25),在假设僵尸可以一次被樱桃炸弹消灭的情况下,消灭所有僵尸的最少阳光消耗量。 输入格式 输入 6 行 9 列数据,其中 1 表示有僵尸,0 表示无僵尸 输出格式 输出 1 个数据,表示消灭所有僵尸的最少阳光消耗量.用c++完成
时间: 2024-04-01 17:37:10 浏览: 29
好的,我来为你解答这道题。
首先,我们可以使用深度优先搜索来枚举所有的樱桃炸弹和荷叶的使用情况。具体来说,我们可以从左到右、从上到下枚举每一个格子,如果这个格子有僵尸,我们就可以尝试使用樱桃炸弹来消灭它,或者使用荷叶来防止它前进。如果这个格子没有僵尸,则我们可以直接跳过。
在搜索的过程中,我们需要记录当前已经使用的阳光消耗量,以及还剩下哪些格子需要消灭僵尸。如果已经消灭完了所有的僵尸,我们就可以更新答案。
最后,我们只需要输出所有搜索过程中的答案的最小值,即为所求的结果。
下面是完整的 C++ 代码实现:
相关问题
梵梵最近在玩 PVZ 泳池关卡,不考虑僵尸的移动以及植物的冷却时间,他想知道只运用樱桃炸弹(消耗阳光 150,樱桃炸弹可以消灭以它为中心周围 9 个格子内的僵尸)和荷叶(消耗阳光 25),在假设僵尸可以一次被樱桃炸弹消灭的情况下,消灭所有僵尸的最少阳光消耗量。
假设 PVZ 泳池关卡中的所有僵尸都可以一次被樱桃炸弹消灭,那么我们可以考虑如下策略来消灭所有僵尸:
1. 在第一行种下荷叶,保护第二行的樱桃炸弹;
2. 在第二行种下一颗樱桃炸弹,消灭第一行和第二行的僵尸;
3. 在第三行种下荷叶,保护第四行的樱桃炸弹;
4. 在第四行种下一颗樱桃炸弹,消灭第三行和第四行的僵尸;
5. 以此类推,直到消灭完所有的僵尸。
根据上述策略,我们需要在每两行之间种植一颗荷叶来保护樱桃炸弹,然后每两行使用一颗樱桃炸弹来消灭这两行和上一行的僵尸。因此,一共需要种植 $n$ 行荷叶和 $\frac{n}{2}$ 颗樱桃炸弹,最少需要的阳光消耗量为:
$$
25n + 75\cdot\frac{n}{2} = 62.5n
$$
因此,如果 PVZ 泳池关卡中的所有僵尸都可以一次被樱桃炸弹消灭,那么消灭所有僵尸的最少阳光消耗量为 62.5n。其中 $n$ 表示关卡中的行数。
泳池关卡地图为6行9列,中间第三第四行为泳道,必须先种荷叶才能种樱桃炸弹
对于这种情况,我们需要对上面的策略进行一定的修改。
首先,由于泳道的存在,我们需要先在第三行和第四行种植荷叶来保护泳道前面的樱桃炸弹。然后,我们可以按照之前的策略每两行种植一颗樱桃炸弹,消灭这两行和上面的僵尸。具体来说,我们可以按照以下步骤进行:
1. 在第三行和第四行种下荷叶,保护第五行的樱桃炸弹;
2. 在第五行种下一颗樱桃炸弹,消灭第三行、第四行和第五行的僵尸;
3. 在第六行种下荷叶,保护第七行的樱桃炸弹;
4. 在第七行种下一颗樱桃炸弹,消灭第六行和第七行的僵尸;
5. 在第一行和第二行之间种下荷叶,保护第三行的樱桃炸弹;
6. 在第三行种下一颗樱桃炸弹,消灭第一行、第二行和第三行的僵尸;
7. 在第四行和第五行之间种下荷叶,保护第六行的樱桃炸弹;
8. 在第六行种下一颗樱桃炸弹,消灭第四行、第五行和第六行的僵尸;
9. 以此类推,直到消灭完所有的僵尸。
根据上述策略,我们需要在每三行之间种植一颗荷叶来保护樱桃炸弹,然后每两三行使用一颗樱桃炸弹来消灭这两三行和上面的僵尸。因此,一共需要种植 $3n-1$ 行荷叶和 $\frac{2n}{3}$ 颗樱桃炸弹,最少需要的阳光消耗量为:
$$
25(3n-1) + 75\cdot\frac{2n}{3} = 100n - 25
$$
因此,如果 PVZ 泳池关卡中的所有僵尸都可以一次被樱桃炸弹消灭,那么消灭所有僵尸的最少阳光消耗量为 100n - 25。其中 $n$ 表示关卡中的行数,对于泳池关卡,$n=6$。