清华大学【玛雅人的密码】--bfs解题

题目描述

玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=<N<=13）该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。

输入描述

输入包含多组测试数据，每组测试数据由两行组成。

第一行为一个整数N，代表字符串的长度（2<=N<=13）。

第二行为一个仅由0、1、2组成的，长度为N的字符串。

输出描述

对于每组测试数据，若可以解出密码，输出最少的移位次数；否则输出-1。

样例输入

5

02120

样例输出

1

解题思路

由题目可以知道，他要求的是输出最少的移位次数，可以考虑用bfs来解决。

bfs格式如下:

对应的伪码如下：

void BFS(Graph* G,int start,Queue<int>* Q){
    int v,w;
    Q→enqueue(start);//初始化队列
    Q→setMark(start,visited);
    while(Q→length()!=0){
        v=Q→dequeue();//取出队首
        Previsit(G,v);//根据题目要求对其做出对应的动作
        for(w=G→first(v);w<G→n();w=G→next(v,w)){
            if(G→getmark(w)==unvisited){
                G→setMark(w,visited);
                Q→enqueue(w);
            }
        }
    }
}
           

而且，这道题有一个陷阱是，如果源字符串本来就有“2012”串，移位次数为0的时候，要注意先判断。

所以在这里用了judge函数来判断字符串是否有“2012”串。

bool judge(string s){//判断字符串中是否有2012
    if(s.find("2012")!=-1)
        return true;
    return false;
}
           

如果源字符串没有包含“2012”串，我们就要开始调用bfs来寻找最小调换次数。

在这里用了两个数据结构，map和queue。

#include<queue>
#include<map>
map<string, int> M;//M[str]表示str经历的交换次数
queue<string> Q;//队列，用于bfs
           

Swap函数用来调换一次相邻字符。

string Swap(string s,int i){//将字符串s的第i位和第i+1位调换位置。
    char temp=s[i+1];
    string news;
    news=s;
    news[i+1]=news[i];
    news[i]=temp;
    return news;
}
           

然后再判断是否有“2012”串，如果没有的话，则push进去队列等待。

int bfs(string s){
    string news;
    M.clear();
    while(Q.size()!=0){
        Q.pop();
    }
    M[s]=0;//代表s的起始交换次数是0
    Q.push(s);
    while(!Q.empty()){
        s=Q.front();//取出队首
        Q.pop();
        for(int i=0;i<s.size()-1;i++){
            news=Swap(s,i);//调换位置的新字符串
            if(M.find(news)==M.end()){//直到结束都没有该键值
                M[news]=M[s]+1;//新字符串多调换了一次
                if(judge(news))
                    return M[news];
                else
                    Q.push(news);
            }
        }
    }
    return -1;
}
           

源码如下：

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

map<string, int> M;//M[str]表示str经历的交换次数
queue<string> Q;//队列，用于bfs

string Swap(string s,int i){//将字符串s的第i位和第i+1位调换位置。
    char temp=s[i+1];
    string news;
    news=s;
    news[i+1]=news[i];
    news[i]=temp;
    return news;
}

bool judge(string s){//判断字符串中是否有2012
    if(s.find("2012")!=-1)
        return true;
    return false;
}

int bfs(string s){
    string news;
    M.clear();
    while(Q.size()!=0){
        Q.pop();
    }
    M[s]=0;//代表s的起始交换次数是0
    Q.push(s);
    while(!Q.empty()){
        s=Q.front();//取出队首
        Q.pop();
        for(int i=0;i<s.size()-1;i++){
            news=Swap(s,i);//调换位置的新字符串
            if(M.find(news)==M.end()){//直到结束都没有该键值
                M[news]=M[s]+1;//新字符串多调换了一次
                if(judge(news))
                    return M[news];
                else
                    Q.push(news);
            }
        }
    }
    return -1;
}

int main(){
    int n;
    while(cin>>n){
        string s;
        cin.get();//吃掉一个换行符
        getline(cin,s);
        int len=s.length();
        if(judge(s)) {cout<<"0"<<endl;}
        else{
            int ans=bfs(s);
            cout<<ans<<endl;
        }
    }
    return 0;
}