当前位置：首页 > article >正文

P2356 弹珠游戏

article 2024/11/14 3:39:42

在这里插入图片描述
铁子们好呀，博主好久没更新了，今天给大家更新一道编程题！！！
题目链接如下：P2356 弹珠游戏
好，接下来，我将从三个方面讲解这道例题。分别是

题目解析
算法原理
代码实现

文章目录

1.题目解析
2.算法原理
3.代码实现

1.题目解析

如图：
在这里插入图片描述
从字面理解题目意思来看： 它想表达的是在一个n * n的数组里面，有若干个敌人要消灭，但是在每个元素中，你只能用弹珠消灭所在行和列的敌人，获得他们的分数之和，然后选择一个位置，使得你击杀的敌人最多。
需要注意的是： 题目要求玩家”不能和敌人在一个地方”，也就是说，玩家需要在一个“安全位置"发射弹珠，才能攻击敌人，如果玩家和敌人在同一位置，那么发射弹珠和敌人发生碰撞啥的。在这种情况下，这个游戏玩家就是无法攻击，或者不符合攻击逻辑。
所以通俗点题目的意思是：找一个没有敌人的位置，从这个位置发射弹珠攻击行和列的敌人。
我们再来看一下题目的输入输出格式吧~ 如下图所示： 1.从输入格式要求来看：如果说有敌人，则为一个正整数，否则为0，通俗点说就是如果某个数组元素的值为0时， 2.从输出格式来看：它说如果没有容身之处的话，则输出“Bad Game!”，那反之有容身之处，也就是说有安全的位置，那么玩家就输出最多分数。 3.那么从上图的输入输出样例：可以看出当遍历到数组第一行的第四个元素，它的值为0，说明他是有”容身之处“的玩家时能通过在那个安全位置用弹珠攻击所在第一行和第四列的敌人的，通过观察可以发现：将第一行和第四列的敌人个数累加为6。同理：第四行第一列元素的也是0，即安全位置，我们将它所在行和所在列的元素累加起来，得到的值也是6。因此最终这个分数最多就是为6。所以输出结果是为6的。

2.算法原理

刚刚我们对题目进行了分析，接下来我们将讲讲这道题的算法原理是什么
如图：这里博主画了一个图，方便铁子们理解理解。这里黑色图片且打枪的那个人是敌人，紫色图片的那个人物是玩家。这里有个点需要注意的是：这里有敌人不一定代表敌人的分数是1,它有可能是其他正整数。通俗点来说，就是表示这个敌人的分数，分数越高，说明敌人的等级越高，敌人越强，那么攻击这个位置的敌人分数也会更高。那这道题：我们可以通过两次遍历就能求出所有可能的得分情况。思路分析如下：我们可以通过创建两个数组row和col数组，进行两次遍历。 1.第一次遍历：就是计算每行和每列敌人分数总和 2.第二次遍历：找到所有的空位置，利用row[i]+col[j]就能计算可得分数，用变量maxx记录row[i]+col[j]的值并更新最大值。

好，相信讲到这里，大家都理解这个题的算法原理吧，可以先把这题写一下，等会再看看博主的代码实现的思路是否和你相同。

3.代码实现

接下来，铁子们，可以看看博主的代码实现，里面有详细的注释，希望大家都能理解里面每一行代码的意思。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n; // 输入矩阵的大小 n

    // 创建一个 n+1 x n+1 的二维 vector，方便使用 1-based 索引
    vector<vector<int>> matrix(n + 1, vector<int>(n + 1)); 

    // 输入矩阵的各个元素
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> matrix[i][j]; // 输入位置 (i, j) 的值
        }
    }

    // 创建两个一维数组 row 和 col，用于存储每行和每列的敌人分数总和
    vector<int> row(n + 1, 0), col(n + 1, 0);

    // 遍历矩阵，计算每行和每列中敌人的分数和
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (matrix[i][j] != 0) { // 如果当前格子有敌人
                row[i] += matrix[i][j]; // 将该敌人的分数加到第 i 行的总分上
                col[j] += matrix[i][j]; // 将该敌人的分数加到第 j 列的总分上
            }
        }
    }

    // 初始化 maxx 为 -1，表示还没有找到有效的容身之地
    int maxx = -1;

    // 遍历整个矩阵，找出分数最大的位置
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (matrix[i][j] == 0) { // 如果当前位置没有敌人
                // 计算这个位置的行和列的敌人总分
                int cur = row[i] + col[j]; 
                maxx = max(maxx, cur); // 更新最大得分
            }
        }
    }

    // 如果 maxx 仍然是 -1，表示没有空位可以容身，输出 "Bad Game!"
    if (maxx == -1) {
        cout << "Bad Game!" << endl;
    } else {
        cout << maxx << endl; // 输出最大分数
    }

    return 0;
}