题解 | 玛雅人的密码

#include <any>
#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>
#include <vector>
using namespace std;
//each string and its exchange times 
struct node {
    string s ;
    int step ;
    node(string str,int n ):s(str),step(n){};
};
//function to get the neighbors
vector<string> getneighbors (node str){
    vector<string > neighbors;
    int n =str.s.length();
    for (int i=0;i<n-1;i++){
        string  cur=str.s;
        swap(cur[i],cur[i+1]);
        neighbors.push_back(cur);
    }
    return neighbors;
}// now we have all the neighbors

// compare function 
bool istarget(const string & str){
    return str.find("2012")!=string::npos;
}
//find the times
int bfs(string initial_str){
    if(istarget(initial_str)) return 0;
    // point!! queue(fifo) to store struct node 
    queue<node> q;
    unordered_set<string> visited;
    q.push(node(initial_str,0));
    visited.insert(initial_str);
    // bfs 
    while (!q.empty()) {
        node cur =q.front();
        q.pop();
        if(istarget(cur.s)) return cur.step;
        vector<string> neighbors=getneighbors(cur);
        for (string s: neighbors){
            // which means we haven't found the string
            if(visited.find(s)==visited.end()){
                visited.insert(s);
                //join in 
                q.push(node(s,cur.step+1));
            }//not coming yet record it
        }
    }
    return -1;
}
int main() {
    int n ;
    while (cin>>n) {
        string input;
        cin >> input;
        int ans = bfs(input);
        cout << ans << endl;
    }
    return 0;
}

涉及到队列的使用和bfs