秦淮区建设局网站,铜梁集团网站建设,天猫商城买卖平台,株洲专业做网站设计的本题思路
纯bfs#xff0c;注意一个字符中有多个相同的可变字符即可。
代码
void solve() {string a,b; cinab; // 读入起始串和结束串vectorpairstring,string mss; // 可能有一个字符串的多个变换规则#xff0c;不能用map#xff0c;…本题思路
纯bfs注意一个字符中有多个相同的可变字符即可。
代码
void solve() {string a,b; cinab; // 读入起始串和结束串vectorpairstring,string mss; // 可能有一个字符串的多个变换规则不能用mapmultimap可以应该string p,qq;while(cinpqq) { // 读入规则mss.push_back({p,qq});}setstring s; // 用一个集合进行判断是否之前存在这种字符串int mi INF; // 所求最小值bool fg false; // 判断是否找到解s.insert(a); // 先将起始串存入queuepairstring, int q; // 队列 --- 字符串 已经变换次数q.push({a,0}); while(q.size()) { // bfs模板auto tmp q.front(); q.pop();if(tmp.vs 10) continue; // 如果大于10次操作直接continuefor(auto t: mss) { // 根据规则进行变换string str tmp.vf; // 上一个已经变换的字符串int pos str.find(t.vf); // 找到该字符串中是否有相应的变换规则// 注意 find()函数返回为size_t类型是ull类型可能溢出用int可以进行隐式转换if(pos -1) continue; // 如果没有find函数返回-1则continueint len str.size(); // 上一个字符串的长度while(pos ! -1 pos len) { // 可能有多个可以进行相应变换的字符串// e.g. abaaaa 变换规则 a - b, a - c, a - dd等string now ; // 用now作为当前变换过的字符串for(int i 0; i pos; i) {now str[i]; // }now t.vs;pos t.vf.size();for(int i pos; i str.size(); i) {now str[i];}// 上面是进行转换if(s.count(now) 0) { // 判断是否已经存在s.insert(now);q.push({now, tmp.vs 1});}if(now b) { // 判断是否等于目标串mi min(mi, tmp.vs 1);fg true;} pos str.find(t.vf, pos);// coutposendl;}}if(fg) break; // 如果找到了可以直接break否则可能会超时}if(mi 10) puts(NO ANSWER!);else coutmi;
}
