{"problem":{"name":"[NOIP 2002 提高组] 字串变换（疑似错题）","description":{"content":"已知有两个字串 $A,B$ 及一组字串变换的规则（至多 $6$ 个规则），形如： - $A_1\\to B_1$。 - $A_2\\to B_2$。 规则的含义为：在 $A$ 中的子串 $A_1$ 可以变换为 $ B_1$，$A_2$ 可以变换为 $B_2\\cdots$。 例如：$A=\\texttt{abcd}$，$B＝\\texttt{xyz}$， 变换规则为： - $\\texttt{abc","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":128000},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP1032"},"statements":[{"statement_type":"Markdown","content":"已知有两个字串 $A,B$ 及一组字串变换的规则（至多 $6$ 个规则），形如：\n\n- $A_1\\to B_1$。\n- $A_2\\to B_2$。\n\n规则的含义为：在 $A$ 中的子串 $A_1$ 可以变换为 $ B_1$，$A_2$ 可以变换为 $B_2\\cdots$。\n\n例如：$A=\\texttt{abcd}$，$B＝\\texttt{xyz}$，\n\n变换规则为：\n\n- $\\texttt{abc}\\rightarrow\\texttt{xu}$，$\\texttt{ud}\\rightarrow\\texttt{y}$，$\\texttt{y}\\rightarrow\\texttt{yz}$。\n\n则此时，$A$ 可以经过一系列的变换变为 $B$，其变换的过程为：\n\n- $\\texttt{abcd}\\rightarrow\\texttt{xud}\\rightarrow\\texttt{xy}\\rightarrow\\texttt{xyz}$。\n\n共进行了 $3$ 次变换，使得 $A$ 变换为 $B$。\n\n## Input\n\n第一行有两个字符串 $A,B$。\n\n接下来若干行，每行有两个字符串 $A_i,B_i$，表示一条变换规则。\n\n## Output\n\n若在 $10$ 步（包含 $10$ 步）以内能将 $A$ 变换为 $B$，则输出最少的变换步数；否则输出 `NO ANSWER!`。\n\n[samples]\n\n## Background\n\n本题不保证存在靠谱的多项式复杂度的做法。测试数据非常的水，各种做法都可以通过，不代表算法正确。因此本题题目和数据仅供参考。\n\n本题为搜索题，本题不接受 hack 数据。[关于此类题目的详细内容](https://www.luogu.com.cn/paste/pf94n89x)\n\n## Note\n\n对于 $100\\%$ 数据，保证所有字符串长度的上限为 $20$。\n\n**【题目来源】**\n\nNOIP 2002 提高组第二题","is_translate":false,"language":"English"}],"meta":{"iden":"LGP1032","tags":["字符串","搜索","2002","NOIP 提高组","广度优先搜索 BFS","剪枝","折半搜索 meet in the middle"],"sample_group":[["abcd xyz\nabc xu\nud y\ny yz\n","3\n"]],"created_at":"2026-03-03 11:09:25"}}