← 返回题目列表

AtCoder · arc011_3

C. 双峰

中文机器翻译题面 查看原题
2013.01.19 21:28 添加“单词只能由小写字母组成”输入限制。
2013.01.20 21:03 修正了单词列表中包含的单词的输入限制条件。

問題文

“Doublet”是欧洲著名的文字游戏。
这通过逐个更改字母将一个单词转换为另一个单词。
例如,当从头换到尾时,4 可以通过文字转换为头→治疗→青色→告诉→高→尾。
编写一个程序,使用给定的单词列表显示双元组转换的过程。
但是,如果可以进行转换,则转换次数必须最少。

入力

输入将以以下形式通过标准输入给出。
first last
N
s_{0}
s_{1}
:
s_{N-1}
  1. 1 上线第一个字 first 和最后一个字 last 由半角空格分隔。
  2. 2 一个整数,表示第 1 行单词列表中包含的单词数 来自行 N(1≦N≦1,000) 。 来自行
  3. 3 从行 N+2 至行 N 行给出了单词列表。
    • 单词列表可以多次包含相同的单词; 还可以包括 first 和最后一个字 last 。
    • 但是第一个字 具有相同 first 和最后一个字 last 的模式可以用作输入。
    • 每个单词的字母数量相同,1 文字以上 30 必须小于或等于字符。
    • 每个单词都是小写字母 仅由 a-z 组成。

出力

如果可以转换, 1 第 1 行中用于转换的字数 输出 k 并继续 k+2 输出转换过程,包括行中的第一个和最后一个单词。
但是,k 必须是最小转换过程。
转换过程是 1 每行 1 只输出一个字。
如果有多个转换过程,则输出哪一个并不重要。
如果第一个和最后一个单词是同一个单词 k=0 。
如果无法转换, 只需输出-1 。
另外,在输出末尾放置一个换行符。

入力例 1

eye lid
4
lie
die
did
dye

出力例 1

3
eye
dye
die
lie
lid
  1. 1 转换中使用的字数显示在第一行。 输出 3 。
  2. 2 行开始,输出转换过程。
    • eye ... 第一个字 first 。
    • dye ... eye的 1 是第一个字符 转换为e从d。 转换为
    • die ... dye的 2 是第一个字符 转换为y从i。 转换为
    • lie ... die的 1 是第一个字符 转换为d从l。 转换为
    • lid ... lie的 3 是第一个字符 转换为e从d。还有最后一句话 last 就这样结束了。

入力例 2

eye eye
4
lie
die
did
dye

出力例 2

0
eye
eye
  • 第一个字 first 和最后一个字 last 匹配,因此用于转换的字数为 0 。
  • 第一个字 first 和最后一个字 last 分别 输出 1 行并退出。

入力例 3

eye lid
4
lie
lip
did
dye

出力例 3

-1
  • 仅使用给定的单词列表 由于无法转换为eye如果要将其更改为输出最多为lid,-1。