C - ダブレット
Editorial
ヨーロッパでよく知られている言葉遊びとして「ダブレット」がある。
これは、ある単語から別の単語へ、一文字ずつ文字を変えていくことによって変換する、というものである。
例えば、head を tail に変える場合、 単語を経由し、head→heal→teal→tell→tall→tailと変換することができる。
与えられた単語リストを用いてダブレットをするとき、変換する過程を表示するプログラムを作成せよ。
ただし、変換することが可能であるならば、その変換回数は最小でなければならない。
入力は以下の形式で標準入力から与えられる。
変換が可能な場合、 行目に変換に用いる単語の個数 を出力し、続く 行で最初の単語と最後の単語を含めた変換過程を出力せよ。
ただし、 が最小となる変換過程でならなければならない。
変換過程は 行につき つの単語のみ出力すること。
変換過程が複数ある場合、どれを出力しても構わない。
最初と最後の単語が同じ単語である場合は である。
変換できない場合には、
また、出力の最後には改行をいれること。
Time Limit: 2 sec / Memory Limit: 256 MB
2013.01.19 21:28 入力の制限に「単語は英小文字のみで構成される」ことを追記しました。
2013.01.20 21:03 入力の制限の、単語リストに含まれる単語の条件を訂正しました。
問題文
これは、ある単語から別の単語へ、一文字ずつ文字を変えていくことによって変換する、というものである。
例えば、head を tail に変える場合、 単語を経由し、head→heal→teal→tell→tall→tailと変換することができる。
与えられた単語リストを用いてダブレットをするとき、変換する過程を表示するプログラムを作成せよ。
ただし、変換することが可能であるならば、その変換回数は最小でなければならない。
入力
- 行目に最初の単語 と、最後の単語 が半角スペースで区切られて与えられる。
- 行目に単語リストに含まれる単語の個数を表す整数 が与えられる。
- 行目から 行目までの 行は単語リストが与えられる。
- 単語リストの中に同じ単語が複数含まれることもあり、単語リストの中に最初の単語 と、最後の単語 が含まれることもある。
- しかし、最初の単語 と、最後の単語 が同じパターンは入力としてありうる。
- 各単語の文字数は全て等しく、 文字以上 文字以下とする。
- 各単語は英小文字
a-z
のみで構成される。
出力
ただし、 が最小となる変換過程でならなければならない。
変換過程は 行につき つの単語のみ出力すること。
変換過程が複数ある場合、どれを出力しても構わない。
最初と最後の単語が同じ単語である場合は である。
変換できない場合には、
-1
とだけ出力せよ。また、出力の最後には改行をいれること。
入力例 1
Copy
- eye lid
- 4
- lie
- die
- did
- dye
eye lid 4 lie die did dye
出力例 1
Copy
- 3
- eye
- dye
- die
- lie
- lid
3 eye dye die lie lid
- 行目には変換に用いる単語数である を出力する。
- 行目以降は変換する過程を出力する。
eye
最初の単語 である。dye
eye
の 文字目であるe
をd
へ変換した。die
dye
の 文字目であるy
をi
へ変換した。lie
die
の 文字目であるd
をl
へ変換した。lid
lie
の 文字目であるe
をd
へ変換した。また、最後の単語 なので終了する。
入力例 2
Copy
- eye eye
- 4
- lie
- die
- did
- dye
eye eye 4 lie die did dye
出力例 2
Copy
- 0
- eye
- eye
0 eye eye
- 最初の単語 と、最後の単語 が一致するので、変換に用いる単語数は である。
- 最初の単語 と、最後の単語 をそれぞれ 行で出力して終了する。
入力例 3
Copy
- eye lid
- 4
- lie
- lip
- did
- dye
eye lid 4 lie lip did dye
出力例 3
Copy
- -1
-1
- 与えられた単語リストのみを用いて
eye
からlid
へ変換することができないので、-1
を出力する。