/*
很裸的一道搜索题啊
我们看这个数据范围就知道不写搜索都对不起出题人了
我们可以直接bfs+判重
判重我们知道，我们可以用hash,set,map等方法来做咯
这里为了好写一点
就用的set映射来判重
(闲的无聊实验证明了一下set会比map慢一点啊Orz)
Orz还是速度还是可以的(不过NOIP最好还是手写hash叭)
然后这样直接bfs就很简单了
基本功吧
整个题目唯一的稍微的难点就在于字符串的处理了
感觉像是在考字符串？
我们怎么找到一个字符串中有没有可以变换的子串然后改变它
OTZ这很麻烦的鬼东西如果用数组的话
但是如果我们用string就很好做了
加上几个string的函数
就跟水题一样如履平地233333
然后随便乱搞叭
嗯就这样了
那段bfs扩展的字串处理有点复杂
也可以用自己的方法搞咯
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
using namespace std;

struct node
{
    string s;
    int step;
};
queue<node> q;
set<string> vis;
string start,to;
string a[15];
string b[15];
int l=1;

void init()
{
    cin>>start>>to;
    while(cin>>a[l]>>b[l])
        l++;
    node t;
    t.step=0;
    t.s=start;
    q.push(t);
}

void bfs()
{
    node t;
    while(!q.empty())
    {
        t=q.front();    q.pop();
        if(t.step>10)
            break;
        if(t.s==to)
        {
            cout<<t.step<<endl;
            return;
        }
        if(!vis.count(t.s))
        {
            vis.insert(t.s);
            for(int i=1;i<=l;i++)
                if(t.s.find(a[i])>=0)
                    for(int j=t.s.find(a[i]);j>=0&&j<=(t.s.length()-a[i].length());j=t.s.find(a[i],j+1))
                    {
                        node w=t;
                        w.step++;
                        w.s.replace(j, a[i].size(), b[i]);
                        q.push(w);
                    }
        }
    }
    cout<<"NO ANSWER!"<<endl;
}

int main()
{
    init();
    bfs();
    return 0;
}
     

低逼格题解。。。
实际上就是字符串BFS

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#include <cstdio>
#include <cstring>
using namespace std;
struct edgedata
{
    string u,v;
};
struct quedata
{
    string str;
    int tmp;
};
queue<quedata> que;
map<string,bool> flag;
edgedata edge[10];
string strs,stre;
char Cstr1[25],Cstr2[25];
int edgesize;
inline bool cmp(string &a,string &b)
{
    if (a.size()!=b.size())
        return 0;
    for (int i=0;i<(int)a.size();i++)
        if (a[i]!=b[i])
            return 0;
    return 1;
}
inline int Read()
{
    scanf("%s%s",Cstr1,Cstr2);
    strs=Cstr1,stre=Cstr2;
    for (edgesize=1;scanf("%s%s",Cstr1,Cstr2)!=EOF;edge[edgesize].u=Cstr1,edge[edgesize++].v=Cstr2);
    return --edgesize;
}
inline int Write(int arg)
{
    if (arg==-1)
        printf("NO ANSWER!\n");
    else
        printf("%d\n",arg);
    return 0;
}
int Push(quedata u,int tmp)
{
    int pushsize=0;
    for (int list=u.str.find(edge[tmp].u);list!=(int)string::npos;list=u.str.find(edge[tmp].u,list+1),pushsize++)
    {
        quedata v=u;
        v.tmp++;
        v.str.erase(list,edge[tmp].u.size());
        v.str.insert(list,edge[tmp].v);
        if (!flag[v.str])
            que.push(v);
        flag[v.str]=1;
    }
    return pushsize;
}
int Bfs()
{
    for (;!que.empty();que.pop());
    quedata U;
    U.str=strs,U.tmp=0;
    que.push(U);
    for (;!que.empty();)
    {
        quedata u=que.front();
        que.pop();
        if (u.tmp>10)
            return -1;
        if (!strcmp(u.str.c_str(),stre.c_str()))
            return u.tmp;
        for (int i=1;i<=edgesize;i++)
            Push(u,i);
    }
    return -1;
}
int main()
{
    Read();
    int ret=Bfs();
    Write(ret);
    return 0;
}

//bfs 和自己写的字符串处理。
```cpp
#include <iostream>
#include<cstring>
#include<algorithm>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <set>
using namespace std;

#define FileIn() freopen("input.txt","r",stdin);
#define SUPER_BREAK() exit(0);
#define test() cout << "OK \n" << flush;
#define WC(x) cout << (x) << " " << flush << endl;

const int MAXLEN = 75;
const int MAX = 7;
char start[MAXLEN],tar[MAXLEN];
char a[MAX][MAXLEN],b[MAX][MAXLEN];
int cnt = 0;
set<string> vis;

struct Node {
string str;
int step = 0;
};

vector<int> hasIt(const string &pattern,char *s2) {
vector<int> v;
int len1 = pattern.length(),len2 = strlen(s2);
for(int i = 0,j = 0; i < len1; ++i) {
if(i + len2 > len1) break;
bool matched = true;
for(j = 0; j < len2; ++j) {
if(s2[j] != pattern[i+j]) {
matched = false;
break;
}
}
if(matched) v.push_back(i);
}
return v;// 返回匹配的下标序列
}

int bfs() {
queue<Node> q;
Node s;
s.str = string(start);
q.push(s);
vis.insert(s.str);

while(!q.empty()) {
Node u = q.front();
q.pop();
if(u.step > 10) return 0;
if(u.str == tar)
return u.step;

vector<int> v;
for(int i = 0; i < cnt; ++i) {
Node nd;
char buf[MAXLEN];
nd.str = u.str;

v = hasIt(u.str,a[i]);
if(v.size()) {
for(int k = 0; k < v.size(); ++k) { //串处理写的比较差
int p = v[k];
strcpy(buf,u.str.c_str());
strcpy(buf+p,b[i]);
if(strlen(buf) > 20) continue;
strcpy(buf+p+strlen(b[i]),u.str.c_str()+p+strlen(a[i]));
if(strlen(buf) > 20) continue;
nd.str = string(buf);

if(!vis.count(nd.str)) {
nd.step = u.step + 1;
q.push(nd);
vis.insert(nd.str);
}
}
}

}
}
return 0;
}

int main(int argc, char const *argv[])
{
// FileIn();
cin >> start >> tar;
while(scanf(" %s %s",a[cnt],b[cnt]) != EOF) cnt ++;

int ans = bfs();
if(ans == 0) cout << "NO ANSWER!";
else cout << ans;
return 0;
}
```

Map判重，单向BFS，一开始数组开小了，Wrong Answer3个点
```
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <map>

using namespace std;

string A, B;

string from[10];
string to[10];
int n = 1;

struct node
{
string s;
int step;
};

queue<node> q;
map<string, int> visit;

void work()
{
int i, j;
while (!q.empty())
{
struct node t;
t = q.front();
q.pop();
if (t.s == B && t.step <= 10)
{
cout<<t.step<<endl;
return;
}
if (t.step > 10)
return;
if (visit[t.s] == 0)
{
visit[t.s] = 1;
for (i = 1; i <= n; i++)
{
if (t.s.find(from[i]) >= 0)
{
for (j = t.s.find(from[i]); j >= 0 && j <= t.s.size() - from[i].size(); j = t.s.find(from[i], j + 1))
{
struct node w;
w = t;
w.step++;
w.s.replace(j, from[i].size(), to[i]);
q.push(w);
}
}
}
}
}
cout<<"NO ANSWER!"<<endl;
}

int main()
{
node e;
cin>>A>>B;
while (cin>>from[n]>>to[n])n++;
n--;
e.s = A;
e.step = 0;
q.push(e);
work();

return 0;
}
```

数据很小不需要剪枝，直接bfs即可
此题用STL做就如同做简单模拟题一样轻松
```c++
#include<iostream>
#include<cstdio>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std;

struct Transform {
string from, to;
Transform (const string &from, const string &to) : from(from), to(to) {}
};

string A, B;
map<string, int> d;
vector<Transform> transforms;

bool bfs () {
queue<string> Q;
Q.push(A);
d[A] = 0;
while (!Q.empty()) {
string u = Q.front(); Q.pop();
if (d[u] > 10) return false;
if (u == B) return true;
for (int i = 0; i < transforms.size(); i++) {
const Transform &tool = transforms[i];
string C;
int p = u.find(tool.from);
while (p != string::npos) {
C = u;
C.replace(p, tool.from.size(), tool.to, 0, tool.to.size());
if (!d.count(C)) {
d[C] = d[u] + 1;
Q.push(C);
}
p = u.find(tool.from, p+1);
}
}
}
return false;
}

int main ()
{
// freopen("in.txt", "r", stdin);
cin >> A >> B;
string from, to;
while (cin >> from >> to) transforms.push_back(Transform(from, to));

if (bfs()) cout << d[B] << "\n";
else cout << "NO ANSWER!\n";
return 0;
}
```

mdzz为什么加上algorithm就编译不过？？窝的Rp啊！！
- 测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
- 测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10
- 测试数据 #2: Accepted, time = 0 ms, mem = 572 KiB, score = 10
- 测试数据 #3: Accepted, time = 0 ms, mem = 624 KiB, score = 10
- 测试数据 #4: Accepted, time = 93 ms, mem = 1080 KiB, score = 10

Accepted, time = 93 ms, mem = 1080 KiB, score = 50
思路：迭代加深搜索+可行性剪枝。如果剩余步数为x时匹配str失败了，记mp[str] = x，那么当下一次匹配str且剩余步数少于mp[str]，就注定失败。
```c++
#include <iostream>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
string from, to;
map<string, int> mp;
string x[20], y[20];
int n = 1;
int lim = 1;
bool dfs(const string& str, const int now_depth)
{
//cout << str << endl;
if (now_depth > lim)
return 0;
if (str == to) return 1;
if (lim - now_depth <= mp[str])
return 0;
//cout << str << endl;
for (int k = 1; k < n; k++) {
string::size_type pp, last = -1;
string tmp = str;
while (1) {
pp = str.find(x[k], last+1);
if (pp != string::npos) {
tmp.replace(pp, x[k].size(), y[k]);
//cout << tmp << endl;
if (dfs(tmp, now_depth+1))
return 1;
//else mp[tmp] = max(mp[tmp], lim - now_depth-1);

tmp = str;
last = pp;
} else break;
}
}
mp[str] = max(mp[str], lim-now_depth);
return 0;
}

int main()
{
cin >> from >> to;
while (cin >> x[n] >> y[n]) n++;
for (; lim <= 10; lim++) {
if(dfs(from, 0)) {
cout << lim << endl;
return 0;
}
}
cout << "NO ANSWER!" << endl;
return 0;
}

坑，这题一个键可以对应多个值，像这样
a->b
a->c
好多次才ac
附代码：
#include<iostream>
#include<string>
#include<cstdio>
#include<map>
#include<queue>
#include<set>
using namespace std;

map<string,set<string> > g;
map<string,int> d;
string a,b;
queue<string> q;

int bfs()
{
q.push(a);
for (d[a]=0;!q.empty();) {
string s=q.front(); q.pop();
if (s==b) return d[s];
if (d[s]>10) return -1;
for (map<string,set<string> >::iterator i=g.begin();i!=g.end();++i) {
string sub=i->first;
for (int j=0;j<s.size();++j) {
if (s.substr(j,sub.size())==sub) {
for (set<string>::iterator it=i->second.begin();it!=i->second.end();++it) {
string v(s.substr(0,j)+*it+s.substr(j+sub.size(),s.size()-j-sub.size()));
//cout<<v<<endl;
if (d.find(v)==d.end()) {
d[v]=d[s]+1;
//cout<<d[v]<<"new state:"<<v<<endl;
q.push(v);
}
}
}
}
}
}
return -1;

}

int main()
{
//freopen("in.txt","r",stdin);
//int j=0;
//string s1("123456"),s2("www"),s3("12");
//cout<<s1.substr(0,j)+s2+s1.substr(j+s3.size(),s1.size()-j-s3.size());
cin>>a>>b;
string t,s;
while (cin>>t) {
//if (t.first==".") break;
string s; cin>>s;
g[t].insert(s);
}
int ans=bfs();
if (ans==-1) cout<<"NO ANSWER!";
else cout<<ans;
return 0;
}

include <iostream> include <cstring> include <map> include <queue> include <algorithm>

using namespace std;
string f[21], t[21], a, b;
map<string, int> ff;
queue<string> q;
int tt = 1;
void bfs(string x)
{
while(!q.empty()) {
string x = q.front();
if(x == b)
return ;
if(ff[x] >= 11) {
q.pop();
continue;
}
for(int i = 1; i < tt; i++) {
int p = x.find(f[i]);
while(p < x.size()) {
string k = "";
k += x.substr(0, p), k += t[i];
k += x.substr(p + f[i].size(), x.size() - p - f[i].size());
if(ff[k] == 0 || ff[x] + 1 < ff[k])
ff[k] = ff[x] + 1, q.push(k);
p = x.find(f[i], p + 1);
}
}
q.pop();
}
}
int main() {
string x, y;
cin >> a >> b;
while(cin >> x >> y)
if(x != y)
f[tt] = x, t[tt++] = y;
q.push(a), ff[a] = 1;
bfs(a);
if(ff[b] == 0)
cout << "NO ANSWER!" << endl;
else
cout << ff[b] - 1 << endl;
return 0;
}
某些小人觉得我不会这么慷慨大方，所以，小人去shi！！！

记录信息
评测状态 Accepted
题目 P1124 字串变换
递交时间 2016-03-21 07:45:29
代码语言 C++
评测机 ShadowShore
消耗时间 279 ms
消耗内存 1532 KiB
评测时间 2016-03-21 07:45:30

评测结果
编译成功

foo.cpp: In function 'void bfs(std::string)':
foo.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p < x.size()) {
^

测试数据 #0: Accepted, time = 15 ms, mem = 576 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 580 KiB, score = 10

测试数据 #3: Accepted, time = 46 ms, mem = 980 KiB, score = 10

测试数据 #4: Accepted, time = 218 ms, mem = 1532 KiB, score = 10

Accepted, time = 279 ms, mem = 1532 KiB, score = 50

代码

include <iostream>

include <cstring>

include <map>

include <queue>

include <algorithm>

using namespace std;
string f[21], t[21], a, b;
map<string, int> ff;
queue<string> q;
int tt = 1;
void bfs(string x)
{
while(!q.empty()) {
string x = q.front();
if(x == b)
return ;
if(ff[x] >= 11) {
q.pop();
continue;
}
for(int i = 1; i < tt; i++) {
int p = x.find(f[i]);
while(p < x.size()) {
string k = "";
k += x.substr(0, p), k += t[i];
k += x.substr(p + f[i].size(), x.size() - p - f[i].size());
if(ff[k] == 0 || ff[x] + 1 < ff[k])
ff[k] = ff[x] + 1, q.push(k);
p = x.find(f[i], p + 1);
}
}
q.pop();
}
}
int main() {
string x, y;
cin >> a >> b;
while(cin >> x >> y)
if(x != y)
f[tt] = x, t[tt++] = y;
q.push(a), ff[a] = 1;
bfs(a);
if(ff[b] == 0)
cout << "NO ANSWER!" << endl;
else
cout << ff[b] - 1 << endl;
return 0;
}

哎，提交了3次。前两次错竟然是忘了把freopen注释掉，哎，郁闷啊。
代码

#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct node
{
char s[30];
int dep;
} list1[5010],list2[5010];
char a[7][30],b[7][30];
int n;
bool check(char *s1,char *s2)
{
if (strlen(s1)!=strlen(s2)) return false;
for (int i=0;i<strlen(s1);i++)
if (s1[i]!=s2[i]) return false;
return true;
}
bool pan1(char *s,int i,int x)
{
for (int j=i;j<i+strlen(a[x]);j++)
if (s[j]!=a[x][j-i]) return false;
return true;
}
bool pan2(char *s,int i,int x)
{
for (int j=i;j<i+strlen(b[x]);j++)
if (s[j]!=b[x][j-i]) return false;
return true;
}
void bfs()
{
int head1,tail1,head2,tail2,k;
head1=tail1=head2=tail2=1;
while (head1<=tail1 && head2<=tail2)
{
if (list1[head1].dep+list2[head2].dep>10)
{
printf("NO ANSWER!\n");
return ;
}
for (int i=0;i<strlen(list1[head1].s);i++)
for (int j=1;j<=n;j++)
if (pan1(list1[head1].s,i,j))
{
tail1++;
for (k=0;k<i;k++) list1[tail1].s[k]=list1[head1].s[k];
for (int l=0;l<strlen(b[j]);l++,k++) list1[tail1].s[k]=b[j][l];
for (int l=i+strlen(a[j]);l<=strlen(list1[head1].s);l++,k++)
list1[tail1].s[k]=list1[head1].s[l];
list1[tail1].s[k]='\0';
list1[tail1].dep=list1[head1].dep+1;
for (k=1;k<=tail1;k++)
if (check(list1[tail1].s,list2[k].s))
{
printf("%d\n",list1[tail1].dep+list2[k].dep);
return ;
}
}

for (int i=0;i<strlen(list2[head2].s);i++)
for (int j=1;j<=n;j++)
if (pan2(list2[head2].s,i,j))
{
tail2++;
for (k=0;k<i;k++) list2[tail2].s[k]=list2[head2].s[k];
for (int l=0;l<strlen(a[j]);l++,k++) list2[tail2].s[k]=a[j][l];
for (int l=i+strlen(b[j]);l<=strlen(list2[head2].s);l++,k++)
list2[tail2].s[k]=list2[head2].s[l];
list2[tail2].s[k]='\0';
list2[tail2].dep=list2[head2].dep+1;
for (k=1;k<=tail1;k++)
if (check(list1[k].s,list2[tail2].s))
{
printf("%d\n",list1[k].dep+list2[tail2].dep);
return ;
}
}
head1++; head2++;
}
printf("NO ANSWER!\n");
}
int main()
{
//freopen("string.in","r",stdin);
//freopen("string.out","w",stdout);
scanf("%s%s",list1[1].s,list2[1].s);
n=1;
while (scanf("%s%s",a[n],b[n])!=EOF) n++;
n--;
list1[1].dep=list2[1].dep=0;
bfs();
return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int MAXN = 50;

int n = 1, len1[MAXN], len2[MAXN];
char list1[MAXN][MAXN], list2[MAXN][MAXN];
vector<char> v;
set<string> st;

struct Status{
int dep;

char s[100];

}first1, first2;

queue<Status> q;

bool check(Status a, Status b){
if(strlen(a.s) != strlen(b.s))
return 0;

for(int i=0; i<strlen(a.s); i++)
if(a.s[i] != b.s[i])
return 0;
return 1;
}

void clear(Status &now){
for(int i=0; i<50; i++)
now.s[i] = '\0';
}

void check(Status tmp, int a, int b){
//int bri = strlen(tmp.s);
//int tot = min(a+len1[b], bri);
for(int i=a; i<a+len1[b]; i++)
if(list1[b][i-a] != tmp.s[i])
return;
v.clear();
Status now;
clear(now);
for(int i=0; i<a; i++)
v.push_back(tmp.s[i]);
for(int i=0; i<len2[b]; i++)
v.push_back(list2[b][i]);
for(int i=a+len1[b]; i<strlen(tmp.s); i++)
v.push_back(tmp.s[i]);
for(int i=0; i<v.size(); i++)
now.s[i] = v[i];
now.dep = tmp.dep + 1;
if(strlen(now.s) > 20)
return;
if(!st.count(now.s)){
q.push(now);
st.insert(now.s);
}
}

void bfs(){
q.push(first1);
while(!q.empty()){
Status now = q.front();
if(now.dep > 10){
printf("NO ANSWER!");
break;
}
if(check(now, first2)){
printf("%d", now.dep);
break;
}
q.pop();
for(int i=0; i<strlen(now.s); i++)
for(int j=1; j<=n; j++)
check(now, i, j);
if(q.empty())
printf("NO ANSWER!");

}
}

int main()
{
FILE *fin = fopen("in.txt", "r");
fscanf(fin, "%s%s", first1.s, first2.s);
while(fscanf(fin, "%s%s", list1[n], list2[n]) != EOF){
len1[n] = strlen(list1[n]);
len2[n] = strlen(list2[n]);
n++;
}
n--;

bfs();
return 0;
}
BFS + set判重

Block code

#include <iostream>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
string f[21], t[21], a, b;
map<string, int> ff;
queue<string> q;
int tt = 1;
void bfs(string x)
{
while(!q.empty()) {
string x = q.front();
if(x == b)
return ;
if(ff[x] >= 11) {
q.pop();
continue;
}
for(int i = 1; i < tt; i++) {
int p = x.find(f[i]);
while(p < x.size()) {
string k = "";
k += x.substr(0, p), k += t[i];
k += x.substr(p + f[i].size(), x.size() - p - f[i].size());
if(ff[k] == 0 || ff[x] + 1 < ff[k])
ff[k] = ff[x] + 1, q.push(k);
p = x.find(f[i], p + 1);
}
}
q.pop();
}
}
int main() {
string x, y;
cin >> a >> b;
while(cin >> x >> y)
if(x != y)
f[tt] = x, t[tt++] = y;
q.push(a), ff[a] = 1;
bfs(a);
if(ff[b] == 0)
cout << "NO ANSWER!" << endl;
else
cout << ff[b] - 1 << endl;
return 0;
}

49行精简代码

const prime:array[1..20] of longint=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71);
type info=record
dep:longint;
str:string;
end;

var
u:info;
d1,d2:array[0..100000] of string;
i,j,head,tail,tot,dep,v,k:longint;
queue:array[0..100000] of info;
s,s1,s2,ts,tts:string;
f:array[0..10000] of longint;
hash:array[-100000000..100000000] of boolean;
function check(str:string):boolean;
var
h:int64;
i:longint;
begin
h:=0;

for i:=1 to length(str) do
begin
h:=((h+ (ord(str[i])-48)*i*i*prime[i]));
if (h>10000000)or(h<-10000000) then
h:=h mod 99999989;
end;
h:=h mod 99999989;
if hash[h] then
exit(false) else
begin
hash[h]:=true;
exit(true);
end;
end;

procedure kmp(A,B:string);
var
i,j,m,n:longint;
P:array[0..1000] of longint;
begin
m:=length(B);
n:=length(A);
P[1]:=0;
j:=0;
for i:=2 to n do
begin
while (j>0) and (A[j+1]<>A[i]) do
j:=P[j];
if A[j+1]=A[i] then
j:=j+1;
P[i]:=j;
end;
j:=0;
v:=0;

for i:=1 to m do
begin
while (j>0) and (A[j+1]<>B[i]) do
j:=P[j];
if A[j+1]=B[i] then j:=j+1;
if j=n then
begin
inc(v);
f[v]:=i-n+1;
j:=P[j];
end;
end;
end;

begin
readln(s);
s1:=copy(s,1,pos(' ',s)-1);
delete(s,1,pos(' ',s));
s2:=s;

tot:=0;
while not eof do
begin
inc(tot);
readln(s);
d1[tot]:=copy(s,1,pos(' ',s)-1);
delete(s,1,pos(' ',s));
d2[tot]:=s;
end;

head:=1;
tail:=1;
queue[1].str:=s1;
queue[1].dep:=0;
while head<=tail do
begin
u:=queue[head];
dep:=queue[head].dep;
inc(head);
if dep>10 then
break;

for j:=1 to tot do
begin

kmp(d1[j],u.str);

if v>0 then
begin
for k:=1 to v do
begin
ts:=u.str;
tts:=copy(ts,1,f[k]-1);
delete(ts,1,f[k]+length(d1[j])-1);
tts:=tts+d2[j]+ts;
if check(tts) then
begin
inc(tail);
queue[tail].str:=tts;
queue[tail].dep:=dep+1;
if tts=s2 then
begin
writeln(queue[tail].dep);
halt;
end;
end;
end;
end;
end;
end;
writeln('NO ANSWER!');
end.

KMP+hash+bfs

program p1124;
var
a:array[1..600000]of longint;
x,y,b:array[1..700000]of string[20];
s,s1:string;
i,j,n,he,ti,k:longint;
begin

readln(s);
b[1]:=copy(s,1,pos(' ',s)-1);delete(s,1,pos(' ',s));s1:=s;
while not eof do
begin
inc(n);
readln(s);
x[n]:=copy(s,1,pos(' ',s)-1);delete(s,1,pos(' ',s));y[n]:=s;
end;
he:=0;ti:=1;
while he<=ti do
begin
inc(he);
if b[he]=s1 then begin writeln(a[he]);halt;end;
if a[he]>10 then begin writeln('NO ANSWER!');halt;end;
for i:=1 to n do if pos(x[i],b[he])>0 then begin
inc(ti);a[ti]:=a[he]+1;
b[ti]:=b[he];insert(y[i],b[ti],pos(x[i],b[ti]));
delete(b[ti],pos(x[i],b[ti]),length(x[i]));
s:=b[he];k:=pos(x[i],s);
delete(s,pos(x[i],s),length(x[i]));
if pos(x[i],s)>0 then
begin
inc(ti);
a[ti]:=a[he]+1;b[ti]:=s;
insert(y[i],b[ti],pos(x[i],b[ti]));
delete(b[ti],pos(x[i],b[ti]),length(x[i]));
insert(x[i],b[ti],k);
end;
end;
end;
end.
纯bfs，不加任何优化，AC

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node
{
char s[30];
int d;
}l1[5010],l2[5010];
main()
{
char a[7][30],b[7][30];
int n=1,h1=1,t1=1,h2=1,t2=1,i,j,k,l;
cin>>l1[1].s>>l2[1].s;
while(scanf("%s%s",a[n],b[n])!=EOF)
n++;
n--;
l1[1].d=l2[1].d=0;
while(h1<=t1&&h2<=t2)
{
if(l1[h1].d+l2[h2].d>10)
{
cout<<"NO ANSWER!";
return 0;
}
for(i=0;i<strlen(l1[h1].s);i++)
for(j=1;j<=n;j++)
if(strncmp(l1[h1].s+i,a[j],strlen(a[j]))==0)
{
t1++;
for(k=0;k<i;k++)
l1[t1].s[k]=l1[h1].s[k];
for(l=0;l<strlen(b[j]);l++,k++)
l1[t1].s[k]=b[j][l];
for(l=i+strlen(a[j]);l<=strlen(l1[h1].s);l++,k++)
l1[t1].s[k]=l1[h1].s[l];
l1[t1].s[k]='\0';
l1[t1].d=l1[h1].d+1;
for(k=1;k<=t1;k++)
if(strcmp(l1[t1].s,l2[k].s)==0)
{
cout<<l1[t1].d+l2[k].d;
return 0;
}
}
for(i=0;i<strlen(l2[h2].s);i++)
for(j=1;j<=n;j++)
if(strncmp(l2[h2].s+i,b[j],strlen(b[j]))==0)
{
t2++;
for(k=0;k<i;k++)
l2[t2].s[k]=l2[h2].s[k];
for(l=0;l<strlen(a[j]);l++,k++)
l2[t2].s[k]=a[j][l];
for(l=i+strlen(b[j]);l<=strlen(l2[h2].s);l++,k++)
l2[t2].s[k]=l2[h2].s[l];
l2[t2].s[k]='\0';
l2[t2].d=l2[h2].d+1;
for(k=1;k<=t1;k++)
if(strcmp(l1[k].s,l2[t2].s)==0)
{
cout<<l1[k].d+l2[t2].d;
return 0;
}
}
h1++;
h2++;
}
cout<<"NO ANSWER!";
}

#code
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
using namespace __gnu_cxx;
string start,end;
vector<string> w1,w2;
int findstr();
int main(int argc, char** argv) {
cin>>start>>end;
string t1,t2;
while(cin>>t1>>t2)
{
w1.push_back(t1);
w2.push_back(t2);
}
int bfs();
int q=bfs();
if(q==-1) cout<<"NO ANSWER!"<<endl;
else cout<<q<<endl;
return 0;
}
int bfs()
{
map<string,int> l;
l[start]=0;
queue<string> q;
q.push(start);
while(!q.empty())
{string n=q.front();
for(int i=0;i!=w1.size();++i)
{int k=0;
while(k<n.size())
{
int p=n.find(w1[i].c_str(),k);
k+=w1[i].size();
if(p==string::npos) break;
string n1;
for(int j=0;j<p;++j)
n1.push_back(n[j]);
for(int j=0;j<w2[i].size();++j)
n1.push_back(w2[i][j]);
for(int j=p+w1[i].size();j<n.size();++j)
n1.push_back(n[j]);
if(l.count(n1)) continue;
else
l.insert(pair<string,int>(n1,l[n]+1));
if(n1==end) return l[n1];
if(l[n1]>10) return -1;
q.push(n1);
}
}
q.pop();
}
return -1;
}
纯STL实现......
注意这么几点：
有可能出现
abaaaba abcdaba
a b
b d
d e
e f
f g
g c
这样的数据
bfs一定要判重
最后要用一句 return-1；兜底防止无解情况
只有59行哦

61行单向BFS+hash，快被这题玩死了

测试数据 #0: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 5764 KiB, score = 10
Accepted, time = 0 ms, mem = 5764 KiB, score = 50

看代码：
var q:array[1..2,1..10000] of string;{正反向队列}
r:array[1..6,1..2] of string;{转换规则}
step:array[1..2,1..1000] of integer;{答案计数}
a,b:string; {初始状态和目标状态}
h,t:array[1..2] of integer;{两个队列指针}
n,change_number:integer;{规则数,转换结果数}
change_list:array[1..20] of string;
step_now:shortint;{现行步数}
function change(var s:string;a,b:string):boolean;{转换}
var p,p_t:longint;
t:string;
begin
change_number:=0;
p:=pos(a,s);
while p<>0 do
begin
t:=s;
delete(t,p,length(a));
insert(b,t,p);
inc(change_number);
change_list[change_number]:=t;
p_t:=pos(a,copy(s,p+1,length(s)));
if p_t=0 then exit(true);
inc(p,p_t);
end;
if (p=0)and(change_number=0) then exit(false);
exit(true);
end;
procedure add(j{队列号},ste{步数}:shortint;x:string);
begin
inc(t[j]);
step[j,t[j]]:=ste;
q[j,t[j]]:=x;
end;
procedure del(j:shortint;var ste:shortint;var s:string);
begin
inc(h[j]);
s:=q[j,h[j]];
ste:=step[j,h[j]];
end;
function find(j:shortint;s:string):boolean;
var i:longint;
begin
for i:=1 to t[3-j] do{是否在逆向搜索队列中出现}
if s=q[3-j,i] then
begin
writeln(step[3-j,i]+step_now+1);{输出解}
halt;
end;
for i:=1 to t[j] do{是在同向队列重复出现}
if s=q[j,i] then exit(true);
exit(false);
end;
procedure init;{输入初始以及目标，还有规则}
var i:integer;
s:string;
begin
i:=0;
fillchar(h,sizeof(h),0);
fillchar(t,sizeof(t),0);
readln(s);
n:=pos(' ',s);
a:=copy(s,1,n-1);
b:=copy(s,n+1,length(s));
while not(eof) do
begin
inc(i);
readln(s);
n:=pos(' ',s);
r[i,1]:=copy(s,1,n-1);
r[i,2]:=copy(s,n+1,length(s));
end;
n:=i;
add(1,0,a);
add(2,0,b);
end;
procedure dbfs;{双向bfs}
var i,j,k:integer;
temp,str:string;
begin
while (t[1]>h[1])or(t[2]>h[2]) do
for j:=1 to 2 do
begin
del(j,step_now,str);{取出队头元素}
for i:=1 to n do{枚举每种转换规则}
begin
temp:=str;
if change(temp,r[i,j],r[i,3-j]) then
for k:=1 to change_number do
if not find(j,change_list[k]) then
add(j,step_now+1,change_list[k]);
if (step[1,h[1]]>=10)and(step[2,h[2]]>=10) then exit;
end;
end;
end;
begin
init;
dbfs;
writeln('NO ANSWER!');
end.

太棒了，不愧是经典题。

通过一题多解，我不仅学习了hash表还学会了双向广搜。

├ 测试数据 01：答案正确... (333ms, 25804KB)

├ 测试数据 02：答案正确... (341ms, 25804KB)

├ 测试数据 03：答案正确... (142ms, 25804KB)

├ 测试数据 04：答案正确... (157ms, 25804KB)

├ 测试数据 05：答案正确... (118ms, 25804KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 1093ms / 25804KB

双向BFS+天然剪枝