codevs 1099_字串变换_bfs

发布于 2019-05-19  8 次阅读


题目描述

已知有两个字串 A,B 及一组字串变换的规则(至多6个规则):
     A1>B1
     A2>B2
  规则的含义为:在 A$中的子串 A1B1、A2B2 …。
    例如:AabcdB=’xyz’
  变换规则为:
    ‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’
  则此时,AB,其变换的过程为:
   ‘abcd’->‘xud’->‘xy’->‘xyz’
  共进行了三次变换,使得 AB。


思路

看数据范围就知道应该可以搜索,然后就暴力bfs开一个map进行判重就可以了


#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define maxn 101
string x[maxn],y[maxn],a,b;
int ans=0,n=0;
struct edge
{
    string str;
    int step;
};
queue t;
map state;
int bfs()
{
    edge st;
    st.str=a;
    st.step=0;
    t.push(st);
    while (!t.empty())
    {
        edge now=t.front();
        t.pop();
        if (now.str==b&&now.step<=10)
        {
            printf("%d\n",now.step);
            return 0;
        }
        if (state[now.str]==0)
        {
            state[now.str]=1;
            for (int i=1;i<=n;i++)
            {
                if (now.str.find(x[i])>=0)
                {
                    for (int j=now.str.find(x[i]);j>=0&&j<=now.str.size()-x[i].size();j=now.str.find(x[i],j+1))
                    {
                        edge l=now;
                        l.step++;
                        l.str.replace(j,x[i].size(),y[i]);
                        t.push(l);
                    }
                }
            }
        }
    }
    printf("NO ANSWER!\n");
}
int main()
{
    cin>>a>>b;
    n=0;
    while (cin>>x[n+1]>>y[n+1]) n++;
    bfs();
}
]]>