比赛场次 483
比赛名称 20201031
比赛状态 已结束比赛成绩
开始时间 2020-10-31 08:00:00
结束时间 2020-10-31 23:00:00
开放分组 全部用户
注释介绍
题目名称 字串变换
输入输出 string.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 8 简单对比
用户 结果 时间 内存 得分
GravatarShallowDream雨梨 AAAAAAAA 0.000 s 0.00 MiB 100
GravatarHarry Potter AAAAAAAE 0.915 s 18.53 MiB 87
Gravatar数声风笛ovo AAAAAAAT 1.049 s 1.33 MiB 87
Gravatar增强型图元文件 AAAATAAT 2.000 s 0.85 MiB 75
Gravatar锝镆氪锂铽 EEAEEAWE 0.425 s 2.60 MiB 25

字串变换

★★   输入文件:string.in   输出文件:string.out   简单对比
时间限制:1 s   内存限制:128 MiB

【问题描述】

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

共进行了三次变换,使得$A$变换为$B$。

【输入格式】

$A$ $B$

$A_1$ $B_1$

$A_2$ $B_2$  |->变换规则

... ... / 

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

【输出格式】

若在$10$步(包含$10$步)以内能将$A$变换为$B$,则输出最少的变换步数;否则输出"$NO ANSWER$!"

【输入样例】

abcd xyz
abc xu
ud y
y yz

【输出样例】

3