题目描述

经典bfs

样例

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
map<string,int> m1;
int n;
string s1;
int res;

int  bfs(string s1)
{
    m1[s1]=0;
    if(s1.find("2012")!=string::npos)  return 0;
    queue<string> q1;
    q1.push(s1);
    while(!q1.empty())
    {
        s1=q1.front();
        string now=s1;  
        q1.pop();
        for(int i=1;i<=n-1;i++)
        {
            swap(s1[i],s1[i+1]);
            if(m1.count(s1)!=0) ;
            else{
               q1.push(s1);    //bfs经典入栈＋更新距离 
               m1[s1]=m1[now]+1;
               if(s1.find("2012")!=string::npos)  return m1[s1];
            }
            swap(s1[i],s1[i+1]);   //恢复成now  
        }
    }
    return -1;
}


int main()
{
    cin>>n;
    cin>>s1;
    s1=" "+s1;
    res=bfs(s1);
    cout<<res;
}