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

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

简单题 提取不重复的整数

可以把输入的数字当成字符串，开一个大小为 的数组记录字符是否出现。
取反可以用 reverse 函数。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int cnt[10] = {};
    reverse(s.begin(), s.end());
    for (auto it : s) {
        if (!cnt[it - '0']) {
            cout << it;
            cnt[it - '0'] = 1;
        }
    }
}

中等题 句子逆序

本题输入的单词数量没有给出，需要注意输入格式。
用 vector<string> 存储输入的单词，方便快捷。
同样，取反可以用 reverse 函数。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<string> words;
    string s;
    while (cin >> s)words.push_back(s);
    reverse(words.begin(), words.end());
    int n = words.size();
    for (int i = 0; i < n; i++)
        cout << words[i] << " \n"[i == n - 1];
    return 0;
}

困难题 迷宫问题

dfs 模版题。
直接从起点开始 dfs 。
用 vector 模拟栈，dfs 到一个点时，将这个点压入栈中，退出 dfs 时将这个点弹出栈。
当走到终点时输出栈中所有元素并退出程序。
技巧：可在网格外圈加一圈 ，省去了边界判断，只需判断 为不能走的单元格即可。
走过的格子也可以改为 ，退出时改回 。

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> stk;
vector<vector<int>> a;
vector<pair<int, int>> f = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int h, w;
void dfs(int x, int y) {
    if (a[x][y])return;
    a[x][y] = 1;
    stk.emplace_back(x, y);
    if (x == h && y == w) {
        for (auto [p, q] : stk)
            cout << "(" << p - 1 << "," << q - 1 << ")\n";
        exit(0);
    }
    for (auto &[dx, dy] : f)
        dfs(x + dx, y + dy);
    a[x][y] = 0;
    stk.pop_back();
}
int main() {
    cin >> h >> w;
    a.assign(h + 2, vector<int>(w + 2, 1));
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            cin >> a[i][j];
    dfs(1, 1);
    return 0;
}