前言

非常感谢 wzc1995 大佬对我的启示，但我还是改不了用map的习惯，于是我就想单纯地用BFS并记录每一种状态对应的
步数但似乎最后一个点过不去，所以就卡了卡时，所以严格来说，这不是一篇正解。但题解不就是不同思维的聚集地
吗？（就像 初音ミク 大佬用了C++库函数做这道题）

题目描述

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

输入样例

abcd xyz
abc xu
ud y
y yz

输出样例

3

思路

用map记录每一个状态的步数，同时判断转移到的状态的步数有没有大于10

C++ 代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>

#define RG register
#define ll long long
#define INF 0x3f3f3f3f

using namespace std;

const int N=24;

map<string,int>dist;

int n,ans;
string a[N],b[N];

queue<string>q;

inline void check(string t)
{
    for (int i=0;i<t.size();i++)
        for (int j=0;j<n;j++)
            if(t.substr(i,a[j].size())==a[j])
            {
                string state=t.substr(0,i)+b[j]+t.substr(i+a[j].size());
                //新合成字串
                if(!dist[state])
                {
                    dist[state]=dist[t]+1;
                    q.push(state);
                }

            }
}//暴力枚举每一种情况 

inline void BFS(string sta,string end)
{
    dist[sta]=0;
    q.push(sta);
    while(q.size())
    {
        string t=q.front();
        q.pop();

        if(dist[t]>10) continue;
        if(t==end)
        {
            ans=dist[end];
            break;
        }

        check(t);
    }
}

int main()
{
    string now,end;

    cin>>now;
    cin>>end;
    while(cin>>a[n]>>b[n]) n++;

    ans=-1;
    BFS(now,end);

    if(ans==-1) puts("NO ANSWER!");
    else printf("%d\n",ans);

    return 0;

}