| 题目名称 | 65. [NOIP 2002]字串变换 |
|---|---|
| 输入输出 | string.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 8 |
| 题目来源 |
 sywgz
于2008-07-17加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：175， 提交：1195， 通过率：14.64% | ||||
 HZOI_蒟蒻一只 |
100 | 0.000 s | 0.00 MiB | C++ |
 Bennettz |
100 | 0.000 s | 0.00 MiB | C++ |
 雾茗 |
100 | 0.000 s | 0.00 MiB | C++ |
 cwystc |
100 | 0.001 s | 0.17 MiB | Pascal |
 E.M.B.E.R |
100 | 0.002 s | 0.17 MiB | Pascal |
 天空非翔 |
100 | 0.002 s | 0.17 MiB | Pascal |
 Loist. |
100 | 0.002 s | 0.67 MiB | Pascal |
|
Loist. |
100 | 0.002 s | 0.67 MiB | Pascal |
 传奇 |
100 | 0.002 s | 0.69 MiB | Pascal |
 Dissolute丶Tokgo |
100 | 0.003 s | 0.31 MiB | C++ |
| 本题关联比赛 | |||
| 暑假培训二 | |||
| 20201031 | |||
| SYOI 专题 6：折半搜索 | |||
| 关于 字串变换 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
双向BFS完美
 蒙牛盐酸乳
2017-11-07 10:20
30楼
| ||||
|
stl太方便了!可惜t了一个点
 XDDD
2017-09-09 09:00
29楼
| ||||
|
| ||||
 Hzoi_Hugh
2017-08-10 18:40
27楼
| ||||
|
双向搜索确实神奇……步数太多的时候就从终点去搜起点，把两边字符串全部调换一下
 Hzoi_moyi
2017-08-10 07:15
26楼
| ||||
|
手打队列别调库
哈希判重不用map | ||||
|
回复 @하루Kiev :
菜逼 HZOI_蒟蒻一只
2017-08-09 14:45
24楼
| ||||
|
这™是什么玩意儿
 Hallmeow
2017-08-09 07:32
23楼
| ||||
|
暴力搜加各种。。各种神剪枝，再加参考数据修改剪枝，再加%大佬的评论，居然A了。。。去学正解。。
| ||||
|
一天不犯傻就奇怪了……又犯傻直接复制粘贴两个方向，没考虑深入情况……
HZOI_蒟蒻一只
2017-08-08 19:13
21楼
| ||||
하루Kiev 
Hzoi_QTY【问题描述】
已知有两个字串$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