清華大學【瑪雅人的密碼】--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;
}