P1032 [NOIP 2002 Senior] String Transformation (suspected wrong problem)

本题不保证存在靠谱的多项式复杂度的做法。测试数据非常的水，各种做法都可以通过，不代表算法正确。因此本题题目和数据仅供参考。 本题为搜索题，本题不接受 hack 数据。[关于此类题目的详细内容](https://www.luogu.com.cn/paste/pf94n89x)

You are given two strings $A, B$ and a set of string transformation rules (at most $6$ rules), of the form: - $A_1 \to B_1$. - $A_2 \to B_2$. The meaning of the rules is: in $A$, a substring $A_1$ can be transformed into $B_1$, $A_2$ can be transformed into $B_2 \cdots$. For example: $A=\texttt{abcd}$, $B=\texttt{xyz}$, with the transformation rules: - $\texttt{abc}\rightarrow\texttt{xu}$, $\texttt{ud}\rightarrow\texttt{y}$, $\texttt{y}\rightarrow\texttt{yz}$. Then $A$ can be transformed into $B$ through a sequence of transformations: - $\texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz}$. A total of $3$ transformations are performed to transform $A$ into $B$.

The first line contains two strings $A, B$. Each of the following lines contains two strings $A_i, B_i$, representing one transformation rule.

If $A$ can be transformed into $B$ within $10$ steps (inclusive), output the minimum number of steps; otherwise, output `NO ANSWER!`.

For $100\%$ of the testdata, the maximum length of all strings is $20$. Source: NOIP 2002 Senior, Problem 2. Translated by ChatGPT 5