BonBonSlick
@BonBonSlick
Vanilla Web Architect

Тест на собеседовании про шахматного коня?

"You have an infinite chessboard, and a knight. The knight starts at [0, 0] and can move [like a knight moves, skipped for brevity]. Given two coordinates on the board, return the least amount of moves the knight has to make to get to that position"


Как я понимаю тут многомерный массив.
У нас координаты по Х и У.
Варианты ходов просчитать довольно просто их всегда всего лишь 8 где сдвиг +2 и +1 по осям. К примеру конь ходит в право ето Х+2 , если направление вверх У-1, вниз У+1 если стартовая точка левый верхний угол как в cocos2d.
Таким образом можно прикинуть исходя из координат к примеру Х=63 и У=31 что конь сделал минимум ходов 31 в правую сторону т.к. для сдвига в право у нас будет Х+2, и особо не важно У-1 или У+1 до самого конца, где надо поставить коня на точку.

Поетому вот ети 2 момента не понятны мне, как поставить коня на точку когда при таких случаях
1 - X = 99, Y = 100 - чет и не чет
2 - Х = 100, У = 99 -
3 - Х = 99, У = 99
4 - Х = 100, У = 100
И надо посчитать общее количество ходов. Пологаю что есть формула кторая это выполняет просто поделив и премножив координаты как-то.

Пример решения пожалуйста на любом языке, на словах такое сложно представить.

5bbv3.png
Скажу сразу, по матану у меня 1/12 было в школе.
  • Вопрос задан
  • 273 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Решение с небольшим перебором случаев, за константу. Но с кучей математики.

Сначала пара простых наблюдений. Можно взять X и Y по модулю и поменять их местами, чтобы X <= Y. Это как бы повороты и отражения всего поля. Сами ходы тоже поворачиваются, но в задаче нужно лишь их количество да и можно при выводе назад преобразовывать ходы, если запомнить, что мы с входными данными делали.

Далее, порядок ходов неважен. Важно лишь количество каждого типа ходов. Поле-то бесконечное. Если бы границы были всегда рядом, то было бы по-другому.

Очевидно, что обратные ходы вы никогда не делаете - т.е. нет смысла делать (+1, +2) а потом (-1, -2).

Т.е. фактически у нас всего 4 переменные - сколько ходов каждого из 4-х типов вы делаете. Возможно отрицательное количество, если мы идем в обратную сторону. Четыре типа - (+2, +1), (+1, +2), (-1, +2), (-2, +1).

Можно составить уравнения:
2a+b-c-2d = X
a+2b+2c+d = Y
|a|+|b|+|c|+|d| -> min

Отсюда
a = (2X-Y+4c+5d)/3
b = (2Y-X-5c-4d)/3

Подходят не любые значение c и d, а только такие, что дают делящееся на 3 число в числителях.

Последнее важное наблюдение - хотя бы одна из переменных не превосходит 3 по модулю в оптимальном ответе. Допустим иначе. Во-первых, очевидно, что sing(a) = sign(b), и sign(c) = sign(d) (иначе 6 ходов 3x(+1,+2)-3x(+2+1) можно заменить на 2 хода (-1,+2)+(-2,1). Аналогично 3x(-1,+2)-3x(-2,+1)=(-1,+2)+(-2,+1)).

В первом случае, все переменные положительные (иначе бы мы не получили Y>=0). Но тогда мы имеем 8 ходов 2x(+2, +1)+2x(+1, +2)+2x(-1, +2)+2x(-2, +1) = (0, 12). Но это можно сделать всего за 6 ходов 3x(-1,+2)+3x(+1,+2). Во втором случае, первые 2 переменные положительные, а вторые 2 отрицательные и мы имеем 8 ходов 2x(+2, +1)+2x(+1, +2)-2x(-1, +2)-2x(-2, +1) = (12, 0). Опять же, эти 8 ходов можно заменить на 6 ходов. Итак, мы уменьшаем количество ходов, пока не получим, что какая-то переменная меньше 3 по модулю.

Итак, мы точно знаем, что в оптимальном ответе хотя бы одна переменная не превосходит 3 по модулю. Переберем, что это за переменная и ее значение. Пусть это c=-3..3. Воспользуемся формулами выше:
a = (2X-Y+4c+5d)/3
b = (2Y-X-5c-4d)/3

Тут c - фиксировано и только d - неизвестная.
Остаток от деления на 3 у d известен, это r=(2Y-X-5c)%3, иначе бы второе уравнение не делилось нацело. Еще надо проверить, что этот остаток подходит в первое уравнение. Перепишем d = 3k+r. Подставим:
a = (2X-Y+4c+5r)/3 + 5k
b = (2Y-X-5c-4r)/3 - 4k
c = -3..3
d = 3k+r
|a|+|b|+3|k| -> min

Можно тупо перебрать k (ведь любое целое k дает какой-то ответ).

А можно нанести на ось 3 значения 0, -(2X-Y+4c+5r)/15, (2Y-X-5c-4r)/12. Отсортировать, получить 4 интервала.
На каждом интервале посмотреть, как раскрывается |a|, |b| и |k|. В итоге вы получите коэффициент перед k +-5+-4+-1. В зависимости от знака нужно брать или левый или правый конец интервала (округленный до целого внутрь интервала - левый вверх, а правый вниз). Не забудьте проверить, что этот интервал вообще содержит целые числа. Подставляете k во все уравнения и находите a, b и d, сравниваете с текущим оптимальным ответом, запоминаете, если надо.

По идее, надо перебрать еще 3 варианта, когда фиксирована a, b или d. Но есть упрощение. Можно же вращать доску как мы хотим, меняя местами X и Y и их знаки. Можно всегда считать, что фиксированная переменная - именно с. Но надо выбрать минимум из ответов для (X,Y), (-X,Y), (Y,X), (-Y, X).

Решение за O(1).

Еще раз, решаем для 4-х или 8-ми вариантов (чтобы не думать) расположения X, Y.
Там перебираем c от -3 до 3. Находим r. Проверяем, что оно подходит в оба уравнения (делится нацело).
Находим 3 точки смены знаков |a|, |b|, |k|, сортируем, смотрим на 4 отрезка. Можно, чтобы не разбирать случаи бесконечности, дописать в сортированный массив points[] любое значение, меньше первого, в начало и любое значение, больше последнего, в конец. Потом смотрим на 4 интервала, считаем знак коэффициента перед k в целевой функции и берем самую левую или самую правую целую точку на интервале в качестве кандидата на ответ. Считаем |a|, |b|, |d|.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@Denioo
Первый же запрос в яндекс выдает видео в подробным решением.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
17 янв. 2021, в 08:35
50000 руб./за проект
17 янв. 2021, в 01:26
100000 руб./за проект
16 янв. 2021, в 22:34
10000 руб./за проект