【NOIp 2002】【BFS+STL】字串变换

描述

已知有两个字串 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。

格式

输入格式

第一行为两个字符串，第二行至文件尾为变换规则 AB A1B1 \ A2B2 |-> 变换规则 … … / 所有字符串长度的上限为 20。

输出格式

若在 10 步（包含 10步）以内能将 A变换为B ，则输出最少的变换步数；否则输出”NO ANSWER!”

代码

BFS…再加上那么一点点STL小技巧、

#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <map> #define INF 1000 using namespace std; struct Trans{ string a,b; Trans(const string &a,const string &b){ this->a=a; this->b=b; } }; int n=1,d[1000],ans=20; string A,B; string a,b; vector<Trans> trans; map<string,int> dic; bool bfs(){ queue<string> q; q.push(A); dic[A]=0; while(!q.empty()){ const string temp=q.front(); q.pop(); if(dic[temp]>10) return false; if(temp==B) { ans=dic[temp]; return true; } for(int i=0;i<(int)trans.size();i++){ int pos=temp.find(trans[i].a); while(pos!=(int)string::npos){ string t2(temp); t2.replace(pos,trans[i].a.length(),trans[i].b); if(dic.count(t2)==0) { q.push(t2); dic[t2]=dic[temp]+1; } pos=temp.find(trans[i].a,pos+1); } } } return false; } int main(){ freopen("in.txt","r",stdin); cin>>A>>B; while(cin>>a>>b) trans.push_back(Trans(a,b)); if(bfs()) printf("%d",ans); else printf("NO ANSWER!"); return 0; }

转载于:https://www.cnblogs.com/leotan0321/p/6081388.html

相关资源：各显卡算力对照表！