牛客春招刷题训练营-2025.4.21题解

d 活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 小红的合数寻找

因为 不是合数，所以 时 一定是合数。
所以除了 不存在答案，其他情况输出 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x;
    cin >> x;
    if (x == 1)cout << -1 << '\n';
    else cout << 2 * x << '\n';
    return 0;
}

中等题 走迷宫

求迷宫中的最短路，考虑bfs（广度优先搜索）。
从 开始bfs，队列存储( 坐标， 坐标，距离起点的距离 )，将 加入队列，在循环中，将与队头格子相邻的未访问格子加入队列，该格子的距离设为队头的 ，并将该格子标记为已访问，然后弹出队头。
如果队头是 ，则输出队头的 。
如果直到循环结束队列为空都未访问到 ，则输出 。

#include <bits/stdc++.h>
using namespace std;
bool vis[1002][1002];
char c[1002][1002];
int main() {
    int n, m;
    cin >> n >> m;
    int xs, ys, xt, yt;
    cin >> xs >> ys >> xt >> yt;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> c[i][j];
    queue<array<int, 3>> q;
    q.push({xs, ys, 0});
    vis[xs][ys] = 1;
    vector<pair<int, int>> f = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    while (!q.empty()) {
        auto [x, y, d] = q.front();
        q.pop();
        if (x == xt && y == yt) {
            cout << d << '\n';
            return 0;
        }
        for (auto [dx, dy] : f) {
            if (!vis[x + dx][y + dy] && c[x + dx][y + dy] == '.') {
                q.push({x + dx, y + dy, d + 1});
                vis[x + dx][y + dy] = true;
            }
        }
    }
    cout << -1 << '\n';
    return 0;
}

困难题 字母收集

观察到数据范围可以动态规划。
设计状态 为走到 格子时最多能获取多少分。
再设 为拿到 格子上的字母可以获得多少分。
拿到 其他字母可以分别获得 分。
因为只能向右或者向下走，那么 的上一步只能是 或 。
转移方程：。
答案为 。

#include <bits/stdc++.h>
using namespace std;
char c[502][502];
int dp[502][502];
int score[128];
int main() {
    int n, m;
    cin >> n >> m;
    score['l'] = 4;
    score['o'] = 3;
    score['v'] = 2;
    score['e'] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> c[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + score[c[i][j]];
    cout << dp[n][m] << '\n';
    return 0;
}