Ханойські вежі#6187
Кожному програмісту відома головоломка «Ханойські вежі». Коротко нагадаємо її умову.
Є стержні: A, B, C. Спочатку дисків різного діаметру знаходяться на стержні A: найменший диск розміщено зверху, далі до низу — за зростанням діаметра. Другий і третій стержні порожні.
Потрібно перемістити всі диски зі стержня A на стержень B, використовуючи C як допоміжний.
За хід дозволяється зняти верхній диск і покласти його або на порожній стержень, або на інший стержень поверх диска більшого діаметру.
Майже всі книжки з програмування містять рекурсивне розв'язання цієї задачі. Нижче наведена процедура на мові Паскаль:
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;
Наприклад, комбінація «BCA» означає, що найменший диск розміщено на стержні B, середній — на стержні C, а найбільший — на стержні A.
Під час підготовки до змагань члени журі іноді грали в цю гру, записуючи поточні комбінації (кожну на окремому аркуші паперу). Проте ці аркуші потім переплутались.
Напишіть програму, яка визначає для кожної комбінації, чи зустрічалась вона у грі, і виводить усі задані комбінації у порядку їх появи у стандартному перебігу гри.
У першому рядку містяться два цілих числа (1 \leq n \leq 250) — кількість дисків, та (1 \leq m \leq 1000) — кількість комбінацій. Кожен з наступних рядків містить комбінацію — рядок з великих літер ("A", "B" чи "C"), що описують розташування дисків на стержнях. Перша (ліва) літера вказує позицію (назву стержня) найменшого диска, друга — другого за розміром, і так далі.
Виведіть рядків — комбінацій, поданих у вхідному файлі, відсортованих згідно з порядком їх появи у перебігу гри.
Приклад 1