#P1032. [NOIP2002 提高组] 字串变换

    ID: 1794 Type: RemoteJudge 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>字符串搜索2002NOIp 提高组广度优先搜索,BFS剪枝

[NOIP2002 提高组] 字串变换

题目背景

本题疑似错题,不保证存在靠谱的多项式复杂度的做法。测试数据非常的水,各种做法都可以通过,不代表算法正确。因此本题题目和数据仅供参考。

题目描述

已知有两个字串 A,BA,B 及一组字串变换的规则(至多 66 个规则),形如:

  • A1B1A_1\to B_1
  • A2B2A_2\to B_2

规则的含义为:在 AA 中的子串 A1A_1 可以变换为 B1 B_1A2A_2 可以变换为 B2B_2\cdots

例如:A=abcdA=\texttt{abcd}BxyzB=\texttt{xyz}

变换规则为:

  • abcxu\texttt{abc}\rightarrow\texttt{xu}udy\texttt{ud}\rightarrow\texttt{y}yyz\texttt{y}\rightarrow\texttt{yz}

则此时,AA 可以经过一系列的变换变为 BB,其变换的过程为:

  • abcdxudxyxyz\texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz}

共进行了 33 次变换,使得 AA 变换为 BB

输入格式

第一行有两个字符串 A,BA,B

接下来若干行,每行有两个字符串 Ai,BiA_i,B_i,表示一条变换规则。

输出格式

若在 1010 步(包含 1010 步)以内能将 AA 变换为 BB,则输出最少的变换步数;否则输出 NO ANSWER!

abcd xyz
abc xu
ud y
y yz

3

提示

对于 100%100\% 数据,保证所有字符串长度的上限为 2020

【题目来源】

NOIP 2002 提高组第二题