可能是find函数的问题叭,因为后面会出现相同的结构,而find只找第一个出现的字串,所以最好手写查找函数(~~可能~~)
by Liveddd @ 2020-09-30 21:20:35
@[杨凯](/user/178128) 我也是同样的问题,就是暴力的时候要剪枝但我不知道该怎么搞
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef map<string,string>::iterator mit;
struct node{
string st;
int step;
};
multimap <string,string> c;
queue <node> q;
string a,b;
int ans=INT_MAX;
void bfs()
{
node t;
t.st=a;
t.step=0;
q.push(t);
while(!q.empty())
{
ans=INT_MAX;
node now=q.front();
cout<<now.st<<endl;
q.pop();
for(mit i=c.begin();i!=c.end();i++)
{
if(now.st.find(i->first)!=string::npos)
{
node temp=now;
temp.st.replace(now.st.find(i->first),(i->first).size(),i->second);
temp.step=now.step+1;
q.push(temp);
}
}
if(now.st==b&&now.step<=10)
{
ans=min(ans,now.step);
}
}
if(ans>10)
{
cout<<"NO ANSWER!";
}
else
{
cout<<ans<<endl;
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin>>a>>b;
string a1,b1;
while(cin>>a1>>b1)
{
c.insert(make_pair(a1,b1));
}
bfs();
return 0;
}
```
by Chinshyo @ 2020-10-18 10:12:06