Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
790. Word Ladder
Поиск в ширину (BFS)Олимпиадные задачи на английском языке
| 08/02/2008 | Тренировка (задачи Benelux APC preliminary 2007) (A) |
| 11/07/2013 | Лето 2013-8 (A) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
A word ladder is a sequence of words, in which two consecutive words differ by exactly
one letter. An example of such a ladder (usually arranged vertically, hence the "ladder")
would be: beer, brew, brow, word, down. Note that to get from one word to the next, the
letters may be rearranged, and exactly one letter is changed.
For this problem, you will be given a dictionary of distinct words, all of the same length.
Your task is to write a program that finds a word ladder of minimal length, such that the
first and last word of the ladder have no letters in common.
Input
On the first line an integer `t` (`1\ ≤\ t\ ≤\ 100`): the number of test cases. Then for each test
case:
- A line with two space-separated integers `n` (`2\ ≤\ n\ ≤\ 100`) and `l` (`1\ ≤\ l\ ≤\ 20`): the number of words and their length.
- `n` lines with a word, each consisting of `l` lowercase letters (a – z).
Output
For each testcase:
- a single line with the words in a ladder of minimal length, separated by a single space.
It is guaranteed that at least one such ladder can be constructed. If there is more than
one, output the one that comes first lexicographically.
Notes
If `s` and `t` are strings of equal length and `s_i` denotes the `i`th character of `s`, then `s` precedes
`t` lexicographically if for some `i`: `s_i\ <\ t_i` and `s_j` = `t_j` for all `j\ <\ i`.
Sample input
1 9 3 alt spy sea opt pea ape spa apt ale
Sample output
ale alt apt opt
