Ханойские башни
Каждому программисту известна головоломка "Ханойские башни". Кратко напомним ее условие.
Имеются 3 стержня: A, B, C. Изначально n дисков разного диаметра находятся на стержне A: наименьший диск расположен сверху, и далее к низу по возрастанию диаметра. Второй и третий стержни пустые.
Необходимо переместить все диски со стержня A на стержень B используя C как дополнительный.
За один шаг разрешается снять 1 верхний диск и положить его либо на пустой стержень, либо на другой стержень на диск с большим диаметром.
Почти все книги по программированию содержат рекурсивное решение этой задачи. Далее приведена процедура на языке Паскаль.
Procedure Hanoi (A, B, C: integer; N:integer);
Begin
If N>0 then
Begin
Hanoi (A, C, B, N-1);
Writeln(‘Disk ’, N, ‘ from ‘, A, ‘ to ‘, B);
Hanoi (C, B, A, N-1)
End
End;
Например, комбинация "BСA" обозначает, что наименьший диск расположен на стержне B, средний на стержне С, а наибольший на стержне A.
Члены жюри, готовясь к соревнованию, иногда играют в эту игру, записывая текущие комбинации (каждую на отдельном листке бумаги). Однако позже все эти листки перемешались.
Напишите программу, которая установит, встречалась ли указанная комбинация в игре.
Входные данные
Первая строка содержит два числа n (1 ≤ n ≤ 250) – число дисков, и m (1 ≤ m ≤ 1000) - количество комбинаций. Следующие m строк содержат m комбинаций. Каждая комбинация состоит из n заглавных букв ("A", "B" или "C") - расположение n дисков на стержнях. Первая (левая) буква указывает на позицию (имя стержня) наименьшего диска, вторая буква - на позицию второго наибольшего диска и так далее.
Выходные данные
Вывести m строк – m комбинаций, отсортированных в порядке их следования в игре.