#101. 字串变换

字串变换

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

A1>B1\red{A_1 -> B_1}

A2>B2\red{A_2 -> B_2}

规则的含义为:在 A\red A 中的子串 A1\red{A_1} 可以变换为 B1\red{B_1}A2\red{A_2} 可以变换为 B2\red{B_2}

例如:A=’abcd\red{A=’abcd’} B=’xyz\red{ B=’xyz’}

变换规则为:

abc>xu\red{‘abc’->‘xu’} ud>y\red{‘ud’->‘y’} y>yz\red{‘y’->‘yz’}

则此时,A\red A 可以经过一系列的变换变为B\red B,其变换的过程为:

abcd>xud>xy>xyz\red{‘abcd’->‘xud’->‘xy’->‘xyz’}

共进行了三次变换,使得A\red A 变换为B\red B

输入格式

输入格式如下:

A\red A B\red B

A1\red{A_1} B1\red{ B_1}

A2\red{A_2} B2\red{B_2}

|-> 变换规则 … … /

所有字符串长度的上限为20\red{ 20}

输出格式

若在 10\red{10} 步(包含10\red{ 10}步)以内能将A\red A 变换为B\red B ,则输出最少的变换步数;否则输出NOANSWER!\red{”NO ANSWER!”}

样例

输入样例

abcd xyz
abc xu
ud y
y yz

输出样例

3

ts提高6

未参加
状态
已结束
规则
IOI
题目
5
开始于
2024-2-2 14:00
结束于
2024-2-2 17:00
持续时间
3 小时
主持人
参赛人数
14