Витя хочет
придумать новую игру с числами. В этой игре от игроков требуется преобразовать
четырёхзначные числа, не содержащие нулей, при помощи следующего разрешённого
набора действий:
1.
Можно увеличить первую цифру числа на 1, если она не равна
9.
2.
Можно уменьшить последнюю цифру на 1, если она не равна 1.
3.
Можно циклически сдвинуть все цифры на одну вправо.
4.
Можно циклически сдвинуть все цифры на одну влево.
Например,
применяя эти правила к числу 1234 можно получить числа 2234, 1233, 4123 и 2341 соответственно.
Точные правила игры Витя пока не придумал, но пока его интересует вопрос, как
получить из одного числа другое за минимальное количество операций.
Вход. Два различных четырёхзначных числа, каждое из которых не
содержит нулей.
Выход. Вывести последовательность четырёхзначных чисел, не
содержащих нулей. Последовательность должна начинаться первым из заданных чисел
и заканчиваться вторым из данных чисел, каждое последующее число в
последовательности должно быть получено из предыдущего числа применением одного
из правил. Количество чисел в последовательности должно быть минимально
возможным.
|
Пример
входа |
Пример
выхода |
|
1234 4321 |
1234 2234 3234 4323 4322 4321 |
графы -
поиск в ширину
Опишем функциями
четыре правила преобразования числа. Запустим поиск в ширину из первого числа.
Как только доберемся до второго (а это обязательно произойдет), процесс поиска
прекращаем. Строим массив предков, чтобы восстановить найденный кратчайший
путь.
Объявим очередь
и дополнительные массивы.
#define MAX 10000
deque<int> d;
int used[MAX], prev[MAX];
Опишем функции
преобразования числа.
int AddOne(int
n)
{
if (n / 1000
!= 9) return n + 1000;
return n;
}
int MinusOne(int
n)
{
if (n % 10 !=
1) return n - 1;
return n;
}
int ShiftLeft(int
n)
{
return (n %
1000) * 10 + n / 1000;
}
int ShiftRight(int
n)
{
return (n %
10) * 1000 + n / 10;
}
Используя массив
предков, выводим путь от стартового числа до n.
void path(int
n)
{
if (n == -1) return;
path(prev[n]);
printf("%d\n",n);
}
Поиском в
глубину ищем кратчайший путь от start
до b.
void bfs(int
start)
{
int v, u, i;
int (*Op[4])(int) = {AddOne, MinusOne, ShiftLeft, ShiftRight};
d.push_front(start); used[start] = 1;
while(!d.empty())
{
u = d.front(); d.pop_front();
Если дошли до b, то останавливаем поиск.
if (u == b)
break;
Перебираем все позиции v, куда можно перейти из u. Если мы еще не были в позиции v, то идем туда (заносим ее в конец
очереди и обновляем ячейки used[v] и
prev[v]).
for(i = 0;
i < 4; i++)
{
v = Op[i](u);
if(!used[v])
{
used[v] = 1;
prev[v] = u;
d.push_back(v);
}
}
}
}
Основная часть
программы. Читаем входные числа.
scanf("%d %d",&a,&b);
memset(used,0,sizeof(used));
memset(prev,-1,sizeof(prev));
Запускаем поиск в глубину и выводим
искомый порядок преобразования.
bfs(a);
path(b);