| 比赛场次 | 606 |
|---|---|
| 比赛名称 | SYOI 专题 6：折半搜索 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2024-04-25 19:00:00 |
| 结束时间 | 2024-04-30 22:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 | 折半搜索，又称为meet-in-the-middle。 主讲人：刘一澈 |
| 题目名称 | 字串变换 |
|---|---|
| 输入输出 | string.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试点数 | 8 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 郑霁桓 |
AAAAAAAA | 0.014 s | 0.75 MiB | 100 |
【问题描述】
已知有两个字串$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