Сортировка бильярдных шаров
Игра "Ротация" — одна из популярных игр в карманный бильярд. В ней используется 15 шаров, пронумерованных от 1 до 15, которые в начале игры располагаются, как показано на рисунке ниже. (Примечание: порядок шаров изменен для упрощения задачи по сравнению с реальными правилами игры "Ротация".)
Вы — инженер, работающий над созданием автоматической бильярдной машины. На первом этапе вам удалось разработать машину, которая устанавливает шары в начальное положение. Этот проект был успешным, и машина может расставлять шары в треугольной форме. Однако, к сожалению, она не может разместить шары в правильном порядке.
Теперь ваша задача — создать другую машину, которая исправляет порядок шаров, меняя их местами. Чтобы минимизировать затраты, разрешается менять местами только шар №1 с соседними шарами, которые не находятся в одном ряду. Например, в приведенном ниже случае можно поменять местами только следующие пары: (1,2), (1,3), (1,8) и (1,9).
Напишите программу, которая вычисляет минимальное количество перестановок, необходимых для исправления порядка.
Входные данные
Первая строка каждого тестового случая содержит целое число N (1 ≤ N ≤ 5), которое обозначает количество рядов.
Следующие N строк описывают, как шары расположены первой машиной; i-я строка содержит ровно i целых чисел, представляющих номера шаров.
Ввод завершается, когда N = 0. В этом случае ваша программа не должна выводить результат.
Выходные данные
Для каждого тестового случая выведите номер случая и минимальное количество перестановок.
Вы можете предположить, что любое расположение можно исправить не более чем за 45 перестановок.