AT_arc011_3 [ARC011C] ダブレット

[problemUrl]: https://atcoder.jp/contests/arc011/tasks/arc011_3 ヨーロッパでよく知られている言葉遊びとして「ダブレット」がある。 これは、ある単語から別の単語へ、一文字ずつ文字を変えていくことによって変換する、というものである。 例えば、head を tail に変える場合、$ 4 $ 単語を経由し、head→heal→teal→tell→tall→tailと変換することができる。 与えられた単語リストを用いてダブレットをするとき、変換する過程を表示するプログラムを作成せよ。 ただし、変換することが可能であるならば、その変換回数は最小でなければならない。 入力は以下の形式で標準入力から与えられる。 > $ first $ $ last $ $ N $ $ s_{0} $ $ s_{1} $ $ : $ $ s_{N-1} $ 1. $ 1 $ 行目に最初の単語 $ first $ と、最後の単語 $ last $ が半角スペースで区切られて与えられる。 2. $ 2 $ 行目に単語リストに含まれる単語の個数を表す整数 $ N(1≦N≦1,000) $ が与えられる。 3. $ 3 $ 行目から $ N+2 $ 行目までの $ N $ 行は単語リストが与えられる。 - 単語リストの中に同じ単語が複数含まれることもあり、単語リストの中に最初の単語 $ first $ と、最後の単語 $ last $ が含まれることもある。 - しかし、最初の単語 $ first $ と、最後の単語 $ last $ が同じパターンは入力としてありうる。 - 各単語の文字数は全て等しく、$ 1 $ 文字以上 $ 30 $ 文字以下とする。 - 各単語は英小文字 `a-z` のみで構成される。 変換が可能な場合、 $ 1 $ 行目に変換に用いる単語の個数 $ k $ を出力し、続く $ k+2 $ 行で最初の単語と最後の単語を含めた変換過程を出力せよ。 ただし、$ k $ が最小となる変換過程でならなければならない。 変換過程は $ 1 $ 行につき $ 1 $ つの単語のみ出力すること。 変換過程が複数ある場合、どれを出力しても構わない。 最初と最後の単語が同じ単語である場合は $ k=0 $ である。 変換できない場合には、`-1` とだけ出力せよ。 また、出力の最後には改行をいれること。 ```

eye lid
4
lie
die
did
dye
```

 ```
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 $ なので終了する。
 
```
eye eye
4
lie
die
did
dye
```

 ```
0
eye
eye
```

- 最初の単語 $ first $ と、最後の単語 $ last $ が一致するので、変換に用いる単語数は $ 0 $ である。
- 最初の単語 $ first $ と、最後の単語 $ last $ をそれぞれ $ 1 $ 行で出力して終了する。
 
```
eye lid
4
lie
lip
did
dye
```

 ```
-1
```

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

N/A

N/A