题解 | 密码锁

#include <bits/stdc++.h>

using namespace std;
typedef struct node{//定义每一种排列的结构体
    int count;
    string str;
    node(int x, string str):count(x),str(str){};
};

using namespace std;
int bfs(string str){
    map<string,bool> m;//定义map记录已出现过的字符串节点
    queue<node> q;
    node temp =  node(0,str);
    q.push(temp);
    m[str]=true;
    while(!q.empty()){
        node first = q.front();
        q.pop();
        string firStr = first.str;
        if(firStr.find("2012")!=firStr.npos){
            return first.count;
        }
        for(int i=0;i<firStr.length()-1;i++){//交换字符
            string str2 = firStr;
            swap(str2[i],str2[i+1]);
            if(m.find(str2)!=m.end()&&m[str2]==true);//已出现过则跳过
            else{//否则入队
                node second = node(first.count+1, str2);
                q.push(second);
                m[str2]=true;
            }
        }
    }
    return -1;
}

int main(){
    int n;
    string str;
    while(cin>>n>>str){
        cout<<bfs(str)<<endl;
    }
}

广搜，学习了评论区的思路，这里的内存很容易爆，数据量极大，因此，我们必须考虑用map辅助存储，否则一定会爆内存。