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

简单题：提取不重复的整数

和之前那道 字符串分隔 一样，考虑一个一个字符就简单得多了，当然这道题是一个一个数位地输出。

#include <iostream>
#include <set>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    set<char> st;
    for(int i=n-1; i>=0; i--) {
        if(!st.count(s[i])) {
            cout << s[i];
            st.insert(s[i]);
        }
    }
}

中等题：句子逆序

C++的STL库有个reverse函数，可以翻转一个vector数组，能直接解决这道题的需求。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    string x;
    vector<string> a;
    while(cin >> x) {
        a.push_back(x);
    }
    reverse(a.begin(), a.end());
    for(string x: a)
        cout << x << " ";
}

困难题：迷宫问题

BFS经典题，建议不擅长BFS的小伙伴们好好消化一下这道题，可以参考一下我代码的框架，作为BFS的一个模版。

其实能用BFS做的题目都很套路，代码写出来其实也会长得差不多，套路就是走一套入队出队流程（在地图外的点、不能走的点或走过的点就跳过）。

不过这道题有个特殊点事需要记录一下有效路径。

我们可以用一个pre来维护一个pair的键值对，可以理解为一个单链表，把路径串起来。同时pre[{x, y}]有没有被赋值，也可以作为该点有没有走过的依据。

因为确保了每个点只会被走过一次，所以 pre[{x, y}] 也是对应一个唯一的前驱节点。那么走到终点之后只要倒着退回去，就能记录下整个有效路径。

PS：由于个人习惯，把地图整体移动为(1, 1)作为起点。（所以输出结果都要-1）

#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
using pii = pair<int, int>;

int main() {
    int h, w;
    cin >> h >>w;
    vector<vector<int>> mp(h+1, vector<int>(w+1));
    for(int i=1; i<=h; i++)
    for(int j=1; j<=w; j++)
        cin >> mp[i][j];
    queue<pii> q;
    q.push({1, 1});
    vector<int> dx = {0, 1, 0, -1};
    vector<int> dy = {1, 0, -1, 0};
    // 记录一下上一个点
    map<pii, pii> pre;
    while(!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for(int i=0; i<4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx > h || yy > w || xx < 1 || yy < 1)
                continue;
            if(mp[xx][yy] == 1 || pre.count({xx, yy}))
                continue;
            q.push({xx, yy});
            pre[{xx, yy}] = {x, y};
        }
    }
    vector<pii> res;
    for(pii i={h, w}; i!=(pii){1, 1}; i=pre[i]) {
        res.push_back(i);
    }
    res.emplace_back(1, 1);
    while(!res.empty()) {
        auto [x, y] = res.back();
        res.pop_back();
        cout << "(" << x-1 << "," << y-1 << ")" << endl;
    }
    return 0;
}