题面

题目描述

已知有两个字串(A,B)及一组字串变换的规则（至多(6)个规则）:

(A_1) -> (B_1)

(A_2) -> (B_2)

规则的含义为：在 (A)中的子串 (A_1) 可以变换为 (B_1)，(A_2) 可以变换为 (B_2) …。

例如：(A)=abcd，(B)＝xyz，

变换规则为：

abc→xu，ud→y，y→yz

则此时，(A)可以经过一系列的变换变为(B)，其变换的过程为：

abcd→xud→xy→xyz。

共进行了(3)次变换，使得(A)变换为(B)。

输入输出格式

输入格式

输入格式如下：

(A) (B)
(A_1) (B_1)
(A_2) (B_2) |-> 变换规则

... ... /

所有字符串长度的上限为(20)。

输出格式

输出至屏幕。格式如下：

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

输入输出样例

样例

输入 #1

abcd xyz
abc xu
ud y
y yz

输出 #1

分析

给定一些变换规则，求最少步数？明显是广搜吧，因为广搜首解最优，只要搜索搜到(B)，输出答案就行。
这道题还可以灵活的运用STL，让码量大幅下降。首先要铺垫几个前置知识：
首先是find，这个函数怎么用呢。来看下面的代码片段：

string str = "To be, or not to be - that is the question.";
str.find("be"); // 3 (To be)的be
str.find("be",4); // 17 （to be)的be

也就是说，a.find(b)的含义是在a字符串中找到第一个字符串b的位置，返回字符串b的第一个字符在字符串a的位置。
a.find(b,pos)的含义是在a字符串中找到在第pos个位置后第一个字符串b的位置，返回字符串b的第一个字符在字符串a的位置。
如果找不到，会返回string :: npos，也就是说a.find(b)如果a字符串中并不包含字符串b，会返回string :: npos，在一些编译器中，它的值为-1，也有可能是4294967295。所以建议直接写string :: npos。
同样的，还有rfind，倒序寻找，这里不再多说。

然后再介绍一个replace，他是什么意思呢，

string str = "He have a dream.";
str.replace(3,4,"has")// He has a dream.

也就是说，a.replace(pos,n,b)的意思是在a字符串中的第pos个位置和后面n个字符替换成字符串b。无返回值哦！

介绍完了也没啥可说的了，上代码咯！

代码

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2020-02-19 11:32:51 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2020-02-19 11:35:07
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <cstdlib>
using namespace std;

const int maxn = 15;

struct node{
    string str;
    int step;
};

string a,b;
string rulea[maxn];
string ruleb[maxn];
int rules = 1;

void bfs(){
    queue<node> q;
    node now;
    now.str = a;
    now.step = 0;
    q.push(now);

    while(!q.empty()){
        now = q.front();
        q.pop();
        for(int i = 1; i <= rules; i++){
            int pos = now.str.find(rulea[i],0);
            while(1){
                if(pos == string::npos) break;
                node nxt;
                nxt.str = now.str;
                nxt.str.replace(pos,rulea[i].size(),ruleb[i]);
                nxt.step = now.step+1;
                if(nxt.str == b){
                    printf("%d
",nxt.step);
                    exit(0);
                }
                if(nxt.step > 10){
                    printf("NO ANSWER!
");
                    exit(0);
                }
                pos = now.str.find(rulea[i],pos+1);
                q.push(nxt);
            }
        }
    }
    printf("NO ANSWER!
");
    return ;
}

int main(){
    cin>>a>>b;
    while(cin>>rulea[rules]&&cin>>ruleb[rules]) rules++;
    rules--;
    bfs();
    return 0;
}

结果

竟然忘记q.push(nxt)，我服了我自己。WA0
AC100

over.