codevs 1099_字串变换_bfs

lzusa 发布于 2019-05-20 1 次阅读

题目描述

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

思路

看数据范围就知道应该可以搜索，然后就暴力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();
}
]]>