C - ダブレット Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

2013.01.19 21:28 入力の制限に「単語は英小文字のみで構成される」ことを追記しました。
2013.01.20 21:03 入力の制限の、単語リストに含まれる単語の条件を訂正しました。

問題文

ヨーロッパでよく知られている言葉遊びとして「ダブレット」がある。
これは、ある単語から別の単語へ、一文字ずつ文字を変えていくことによって変換する、というものである。
例えば、head を tail に変える場合、44 単語を経由し、head→heal→teal→tell→tall→tailと変換することができる。
与えられた単語リストを用いてダブレットをするとき、変換する過程を表示するプログラムを作成せよ。
ただし、変換することが可能であるならば、その変換回数は最小でなければならない。

入力

入力は以下の形式で標準入力から与えられる。
firstfirst lastlast
NN
s0s_{0}
s1s_{1}
::
sN1s_{N-1}
  1. 11 行目に最初の単語 firstfirst と、最後の単語 lastlast が半角スペースで区切られて与えられる。
  2. 22 行目に単語リストに含まれる単語の個数を表す整数 N(1N1,000)N(1≦N≦1,000) が与えられる。
  3. 33 行目から N+2N+2 行目までの NN 行は単語リストが与えられる。
    • 単語リストの中に同じ単語が複数含まれることもあり、単語リストの中に最初の単語 firstfirst と、最後の単語 lastlast が含まれることもある。
    • しかし、最初の単語 firstfirst と、最後の単語 lastlast が同じパターンは入力としてありうる。
    • 各単語の文字数は全て等しく、11 文字以上 3030 文字以下とする。
    • 各単語は英小文字 a-z のみで構成される。

出力

変換が可能な場合、 11 行目に変換に用いる単語の個数 kk を出力し、続く k+2k+2 行で最初の単語と最後の単語を含めた変換過程を出力せよ。
ただし、kk が最小となる変換過程でならなければならない。
変換過程は 11 行につき 11 つの単語のみ出力すること。
変換過程が複数ある場合、どれを出力しても構わない。
最初と最後の単語が同じ単語である場合は k=0k=0 である。
変換できない場合には、-1 とだけ出力せよ。
また、出力の最後には改行をいれること。

入力例 1

Copy
  1. eye lid
  2. 4
  3. lie
  4. die
  5. did
  6. dye
eye lid
4
lie
die
did
dye

出力例 1

Copy
  1. 3
  2. eye
  3. dye
  4. die
  5. lie
  6. lid
3
eye
dye
die
lie
lid
  1. 11 行目には変換に用いる単語数である 33 を出力する。
  2. 22 行目以降は変換する過程を出力する。
    • eye ...... 最初の単語 firstfirst である。
    • dye ...... eye11 文字目であるedへ変換した。
    • die ...... dye22 文字目であるyiへ変換した。
    • lie ...... die11 文字目であるdlへ変換した。
    • lid ...... lie33 文字目であるedへ変換した。また、最後の単語 lastlast なので終了する。

入力例 2

Copy
  1. eye eye
  2. 4
  3. lie
  4. die
  5. did
  6. dye
eye eye
4
lie
die
did
dye

出力例 2

Copy
  1. 0
  2. eye
  3. eye
0
eye
eye
  • 最初の単語 firstfirst と、最後の単語 lastlast が一致するので、変換に用いる単語数は 00 である。
  • 最初の単語 firstfirst と、最後の単語 lastlast をそれぞれ 11 行で出力して終了する。

入力例 3

Copy
  1. eye lid
  2. 4
  3. lie
  4. lip
  5. did
  6. dye
eye lid
4
lie
lip
did
dye

出力例 3

Copy
  1. -1
-1
  • 与えられた単語リストのみを用いてeyeからlidへ変換することができないので、-1を出力する。


2025-01-20 (Mon)
20:19:24 +00:00