[COGS 0065][NOIP 2002] 字串變換

65. [NOIP2002] 字串變換

★★?? 輸入文件：string.in?? 輸出文件：string.out???簡單對比
時間限制：1 s?? 內存限制：128 MB

[問題描述]

已知有兩個字串A\$, B\$及一組字串變換的規則（至多6個規則）:

A1\$?-> B1\$

A2\$?-> B2\$

規則的含義為：在A\$中的子串A1\$可以變換為B1\$、A2\$可以變換為B2\$…。

例如：A\$＝'abcd' ?B\$＝'xyz'

變換規則為：‘abc’->‘xu’　‘ud’->‘y’　‘y’->‘yz’

則此時，A\$可以經過一系列的變換變為B\$，其變換的過程為：

‘abcd’->‘xud’->‘xy’->‘xyz’

共進行了三次變換，使得A$變換為B$。

[輸入]

A\$?B\$

A1\$?B1\$

A2\$?B2\$? |->變換規則

... ... /?

所有字符串長度的上限為20。

[輸出]

若在10步（包含10步）以內能將A\$變換為B\$，則輸出最少的變換步數；否則輸出"NO ANSWER!"

[輸入樣例]

abcd xyz
abc xu
ud y
y yz

[輸出樣例]

3

?依然是大力暴搜...

單向 $BFS$ 的話開一個隊列, 先把原串懟進去, 然后每次取隊首字符串并嘗試應用變換規則. 每應用成功一個變換后將變換后的字符串再懟回隊列里. 一直重復直至變換得到待求串或者隊列為空. 如果隊列為空則說明不存在解. 用 $STL$ 里的 $std::string,std::pair,std::map$ 食用即可.

雙向 $BFS$ 的話就從兩端對稱搜索, 但是深度限制在 $10$ 以內可能并不會顯得多快OwO...

附雙向 $BFS$ 的參考實現:

GitHub

#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

typedef std::pair<std::string,int> pr;

int n;
int m;
int ans;
std::string from,to;
std::queue<pr> q1,q2;
std::string transform[10][2];
std::map<std::string,int> m1,m2;
std::pair<std::string,int> p1,p2;

bool Search();
void Initialize();
std::string Replace(std::string,int,int,std::string);

int main(){
    Initialize();
    if(Search())
        std::cout<<ans<<std::endl;
    else
        std::cout<<"NO ANSWER!"<<std::endl;
    return 0;
}

bool Search(){
    int len,lenp;
    while((!q1.empty())&&(!q2.empty())){
        p1=q1.front();
        len=p1.first.size();
        for(int i=0;i<len;i++){
            for(int j=0;j<m;j++){
                lenp=transform[j][0].size();
                if(i+lenp<=len&&p1.first.compare(i,lenp,transform[j][0])==0&&m1.count(Replace(p1.first,i,lenp,transform[j][1]))==0){
                    p2.first=Replace(p1.first,i,lenp,transform[j][1]);
                    p2.second=q1.front().second+1;
                    if(p2.second>10)
                        return false;
                    m1[p2.first]=p2.second;
                    q1.push(p2);
                    if(m2.count(p2.first)){
                        ans=p2.second+m2[p2.first];
                        return true;
                    }
                }
            }
        }
        q1.pop();
        p1=q2.front();
        len=p1.first.size();
        for(int i=0;i<len;i++){
            for(int j=0;j<m;j++){
                lenp=transform[j][1].size();
                if(i+lenp<=len&&p1.first.compare(i,lenp,transform[j][1])==0&&m2.count(Replace(p1.first,i,lenp,transform[j][0]))==0){
                    p2.first=Replace(p1.first,i,lenp,transform[j][0]);
                    p2.second=q2.front().second+1;
                    if(p2.second>10)
                        return false;
                    m2[p2.first]=p2.second;
                    q2.push(p2);
                    if(m1.count(p2.first)){
                        ans=p2.second+m1[p2.first];
                        return true;
                    }
                }
            }
        }
        q2.pop();
    }
    return false;
}

void Initialize(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cin>>from>>to;
    while(std::cin>>transform[m][0]>>transform[m][1])
        m++;
    m1[from]=0;
    m2[to]=0;
    q1.push(std::make_pair(from,0));
    q2.push(std::make_pair(to,0));
}

inline std::string Replace(std::string s, int pos,int len,std::string p){
    return s.replace(pos,len,p);
}

?