题解 | #玛雅人的密码#

• 暴力BFS

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

struct pass{
  string s;
  int x;//移动次数
  pass(string s,int x):s(s),x(x){}
};

int bfs(string s){
   pass first(s,0);
   queue<pass>myque;
   myque.push(first);//初始入队
   
   while(!myque.empty()){
     pass cur=myque.front();
     myque.pop();
     if(cur.s.find("2012")!=-1){//查找2012
       return cur.x;
     }
     for(int i=0;i<s.size()-1;i++){
       pass next(cur.s,cur.x+1);
       if(next.s[i]!=next.s[i+1]){//相同无需移动
         swap(next.s[i],next.s[i+1]);
         myque.push(next);
       }
     }
   }
    return -1;
}
 int main(){
   int n;
   string s;
   while(cin>>n>>s){
     int count1=0,count2=0,count0=0;
     for(int i=0;i<n;i++){//统计0、1、2出现次数 排除查找不到的可能
       if(s[i]=='0')count0++;
       else if(s[i]=='1')count1++;
       else if(s[i]=='2')count2++;
     }
     if(count0>=1&&count1>=1&&count2>=2)printf("%d\n",bfs(s));
     else printf("-1\n");
   }
   return 0;
 }
 
 

- 使用map避免重复入队

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;

struct pass{
  string s;
  int x;
  pass(string s,int x):s(s),x(x){}
};

int bfs(string s){
   map<string,bool>visit;//
   pass first(s,0);
   queue<pass>myque;
   myque.push(first);
   visit[s]=true;//标记为已查找过
    
   while(!myque.empty()){
     pass cur=myque.front();
     myque.pop();
     if(cur.s.find("2012")!=-1){
       return cur.x;
     }
     for(int i=0;i<s.size()-1;i++){
       pass next(cur.s,cur.x+1);
       swap(next.s[i],next.s[i+1]);
       if(visit.find(next.s)==visit.end()){//未查找过则入队
           myque.push(next);
           visit[next.s]=true;//标记为已查找过
       }
     }
   }
    return -1;
}
 int main(){
   int n;
   string s;
   while(cin>>n>>s){
     printf("%d\n",bfs(s));
   }
   return 0;
 }