梵梵最近在玩 PVZ 泳池关卡,不考虑僵尸的移动以及植物的冷却时间,他想知道只运用樱桃炸弹(消耗阳光 150,樱桃炸弹可以消灭以它为中心周围 9 个格子内的僵尸)和荷叶(消耗阳光 25),在假设僵尸可以一次被樱桃炸弹消灭的情况下,消灭所有僵尸的最少阳光消耗量。要求用C++写代码
时间: 2024-03-22 17:40:55 浏览: 193
好的,我明白了。这是一个经典的最小化问题,可以使用贪心算法来解决。我们可以从左到右扫描每一列,如果该列上有僵尸且樱桃炸弹可以消灭它,我们就使用樱桃炸弹消灭该列上的所有僵尸。如果该列上没有僵尸,我们就在该列上种植荷叶。最后,我们需要计算使用樱桃炸弹和荷叶的总阳光消耗量。
下面是实现该算法的 C++ 代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> zombies = {
{0, 1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 1, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 1, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 1, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 1, 0, 0, 0, 1}
};
int n = zombies.size();
int m = zombies[0].size();
int cherry_cost = 150;
int lily_pad_cost = 25;
int total_cost = 0;
for (int j = 0; j < m; j++) {
bool has_zombie = false;
for (int i = 0; i < n; i++) {
if (zombies[i][j] == 1) {
has_zombie = true;
break;
}
}
if (has_zombie) {
total_cost += cherry_cost;
for (int i = 0; i < n; i++) {
if (zombies[i][j] == 1) {
zombies[i][j] = 0;
if (i > 0) zombies[i - 1][j] = 0;
if (i < n - 1) zombies[i + 1][j] = 0;
if (j > 0) zombies[i][j - 1] = 0;
if (j < m - 1) zombies[i][j + 1] = 0;
}
}
} else {
total_cost += lily_pad_cost;
}
}
cout << "Total cost: " << total_cost << endl;
return 0;
}
```
在这个代码中,我们使用了一个二维数组 `zombies` 来表示游戏场景中的僵尸分布。其中每个元素的值为 0 或 1,表示该位置上是否有僵尸。变量 `n` 和 `m` 分别表示场景的行数和列数。变量 `cherry_cost` 和 `lily_pad_cost` 分别表示樱桃炸弹和荷叶的阳光消耗量。变量 `total_cost` 记录了使用樱桃炸弹和荷叶的总阳光消耗量。
在主循环中,我们首先扫描每一列,如果该列上有僵尸,我们就使用樱桃炸弹消灭该列上的所有僵尸,并更新二维数组 `zombies`。如果该列上没有僵尸,我们就在该列上种植荷叶,并将荷叶的阳光消耗量加入到 `total_cost` 中。
最后,我们输出 `total_cost` 即可得到答案。
阅读全文