青岛网站建设最便宜,应用商城app下载,网站安全检测百度,大公司外包岗位值得做吗正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1032 题目大意
给若干个变化规则#xff0c;表示A中的axa_xax子串可以变化为bxb_xbx中的子串#xff0c;求至少要多少次变化才可以变为B子串。 解题思路
暴力广搜用mapmapmap库判重。 codecod…正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1032 题目大意
给若干个变化规则表示A中的axa_xax子串可以变化为bxb_xbx中的子串求至少要多少次变化才可以变为B子串。 解题思路
暴力广搜用mapmapmap库判重。 codecodecode
#includeiostream
#includecstdio
#includestring
#includemap
#includequeue
using namespace std;
queuestring q;
mapstring,int d;
string s,ans,a[7],b[7];
int n;
bool cmps(string s,string a,int first,int len)
{for(int i0;ilen;i)if(s[firsti]!a[i]) return false;//couts a first lenendl;return true;
}
int bfs()
{q.push(s);d[s]0;while(!q.empty()){string xq.front();if(d[q.front()]10) {q.pop();continue;}for(int j1;jn;j)for(int i0;ix.size();i)if(cmps(x,a[j],i,a[j].size())){x.erase(i,a[j].size());x.insert(i,b[j]);if(!d[x]){d[x]d[q.front()]1;q.push(x);if(xans) return d[x];}xq.front();}q.pop(); }return -1;
}
int main()
{cinsans;n1;if(sans){printf(0);return 0;}while(cina[n]b[n]) n;n--;int answerbfs();if(answer-1) printf(NO ANSWER!);else printf(%d,answer);
}
