310 - L--system

描述：题意很简单，不过要是想要通过看题明白确实挺麻烦的，就是给你一个开始字符串w和最终字符串z，字符串中只有a与b，如果遇到a就替换成第一个字符串，遇到b就替换成第二个字符串，问这样的替换方式能否构成一个形如 xzy 的字符串(x,y,可为空)；#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <string>using namespace std;#define MAX 130000map<string,int> hash;string a,b,w,z,s[MAX];int flag,rear=1,front=0;void judge(string &p){    for(int i=0; i<p.size(); i++)    {        string str="";        for(int j=i; j<i+z.size()&&j<p.size(); j++) str+=p[j];        if(str==z)        {            printf("YES\n");            flag=1;            return;        }        if(!hash[str])        {            hash[str]=1;            s[rear++]=str;        }    }}void bfs(){    hash.clear();    s[0]=w;    hash[w]=rear=1;    front=0;    if(s[front].size()>=z.size()) judge(s[front]);    if(!flag) while(front<rear)        {            string str="";            for(int i=0; i<s[front].size(); i++)                if(s[front][i]=='a') str+=a;                else str+=b;            judge(str);            if(flag) return;            front++;        }}int main(){#ifndef ONLINE_JUDGE    freopen("a.txt", "r", stdin);#endif    while(cin>>a>>b>>w>>z)    {        flag=0;        bfs();        if(!flag) printf("NO\n");    }    return 0;}