C++ 代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;
queue<string> q;   // 存储每一步骤
unordered_map<string, int> tim; // 存储历史路径及其步骤数
string endstr = "2012", start;
int n;

int bfs(string start)
{
    q.push(start);
    tim.insert({start, 0}); // or  tim[start] = 0;
    int times;

    while(q.size()) // or  !q.empty()
    {
        string str = q.front();
        q.pop();
        times = tim[str];   
        if(str.find(endstr) != string::npos) return times;  //一旦子串存在endstr即刻return
        for(int i = 0; i < n - 1; i++)
        {
            swap(str[i], str[i + 1]);
            if(!tim.count(str)) // 查找是否存在同形 避免循环(禁全同)
            {
                q.push(str);
                tim[str] = times + 1;
            }
            swap(str[i], str[i + 1]); //恢复str进行下一for循环
        }
    }
    return -1;  //不存在解决方案
}

int main()
{
    cin >> n >> start;
    cout << bfs(start) << endl;
    //if(start.find(endstr) != string::npos) cout << '!';//子串存在2012
    //else  cout << '@';//不存在
    return 0;
}