Задача из Моего Собеседования в Amazon - Поиск в Ширину
Vložit
- čas přidán 24. 03. 2024
- Разбираем задачу из моего первого собеседования в Amazon. Я устраивался на позицию Junior Backend в Берлинский офис.
Задача решается с помощью известного алгоритма BFS (поиск в ширину).
Эта задача на Leetcode (требуется premium подписка): leetcode.com/problems/minimum...
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
С анимацией отлично получилось.
Очень интересно смотреть твои разборы задач + тембр и подача приятные.
Если позволяет время - пиши побольше видео.
Увидимся через полтора года!
Почему полтора года?
@@rockkley9159 потому что видео на этом канале выходят по особому алгоритму
Ну как успехи?
полтора года прошли уже, чо как?
@@opalevгде они прошли
Никогда даже не хотел понимать задачи с шахматной доской , после просмотра понял алгоритм 💪🏾
Саша анимация вообще супер!!! Видео было настолько интересным что ни секунды не промотал. Спасибо за такое понятное и четкое объяснение
Долго тебя не было, рад новому видео!
Выпускай чаще пожалуйста, ты лучший мой мотиватор )))
Мощно ты запарился за анимации!) Но получилось явно очень наглядно и понятно!
Спасибо! Отличное видео, интересная задача! Ждем новых роликов.
Спасибо за задачу! Очень подробно объяснил)
Вау, очень крутое и понятное объяснение. Анимация - огонь
Для всех, кто пишет что в алгоритме ошибка, так как мы смотрим только на предыдущий слой и теряем информацию о предыдущих слоях:
На самом деле ошибки нет, вероятно комментаторы путают с алгоритмом DFS или вариантом BFS на очереди (где нужно запоминать все посещенные вершины).
Почему этот алгоритм корректен? Если предположить что на текущем шаге мы попытаемся пойти из ячейки X в ячейку Y, в которой уже были, но которая лежит не в предыдущем слое, то значит она лежит в предпредыдущем или более ранних слоях. Но тогда мы бы перешли по этому ребру Y - X в тот момент, когда рассматривали эту клетку Y и в этом случае X лежало бы не в текущем слое, а в следующем за слоем, в котором лежит Y. Но в предположении X лежит именно в текущем, а Y лежит не в предыдущем. Значит предположение неверно, а значит достаточно рассматривать для клеток, которые мы хотим посетить, лежат ли они в предыдущем слое. И этого будет достаточно.
Более простое объяснение: предыдущий слой это как бы затычка для пути назад. А поскольку это поиск в ширину, то мы эти затычки ставим для всех возможных путей назад, то есть как не старайся не получится "обойти" предыдущий слой со стороны.
Аналогия такая: два длинных коридора с дверьми, которые иногда пересекаются. Ты и твой друг идете одновременно от начала корридоров, и закрываете за собой каждую дверь. Так вот ты не сможешь в месте пересечения коридора пойти назад, т.к. твой друг уже закрыл за собой предыдущуб дверь. При этом не важно сколько до этого дверей было закрыто, главное что он последнюю закрыл в том месте, где вы встретились, поэтому ты не сможешь через его коридор пойти назад, и ты будешь вынужден пойти дальше вперед
@@Abingususчет объяснение намного запутаннее, чем первый коммент)
Спасибо за объяснение. А для тех кто считает, что лучше один раз увидеть. Посмотрите на доску на которой Саша показал уже 3-й слой (4:08). Где-нибудь можно попасть с клетки 3-го слоя на клетку слоя 0 или 1.
Спасибо за видео. На курсах по изучению Пайтон решал эту же задачу:)) интересно посмотреть твое решение. Лайк
Анимация наглядная, круто!
Если брать очень большое поле, то для общего случая нахождения кратчайшего пути стоит добавит разбивку на сектора.
В случае с конем можно сделать еще проще, первые ходы должны делаться с учетом кратчайшей дистанции, и только начиная с дистанции в 4 клетки выполнять обозначенный автором кульбит
Вот я тоже думаю, обход поля n*n это O(n^2), но кажется можно за линейную сложность. Типа мы можем просчитать окрестность исходной точки, потом из каждой точки окрестности сделать простой алгоритм, который примерно
1. Находит два необходимых вида шагов O(1)
2. Считает необходимое колво шагов O(1) k
3. Находит точное количества шагов для шага типа1 и типа2 (линейный поиск O(n), т.к суммарно шагов тип1+тип2 = k точно меньше 2n), и если ответ нашелся, значит это будет тип1+тип2+шаг окрестности. Если не нашелся, значит забиваем на эту точку окрестности
4. Повторяем для каждой точки окрестности и ищем минимальное среди ответов O(c), с количество точек в окрестности
Итого у на фиксированная окрестность а количество шагов растет линейно, значит сложность лин поиска тоже растет линейно.
Также заметим, что порядок шагов тип1 и тип2 не важен, так что тут все ок.
Да, с динамическим программированием получится эффективнее.
очень интересная задача. хорошо рассказано. выпускай ролики чаще
Задача класс! Больше подобного контента!
Блин! точно! это же графы! спасибо большое!
Спасибо, хорошая задача и разбор
круто, спасибо за видосы!
С анимацией хорошо получилось, пожалуйста, делай больше видео
Блин, смотрю каждое твое видео. Спасибо за контент. Тоже мечтаю попасть в google
мечтать мало, нужно работать над собой, чтоб туда попасть
эта задача очень лёгкая
Congrats Alex! Good explanation.
Here is a point you can deal better with:
You were java dev, and you use java terminology in your verbal explanations, but code is written in python. So little fellas can easily miss those word about hashed collection.
Hope you'll continue doing videos like this)
онглечанен, ставит скобку после текста 😂
Спасибо за задачу
Здесь можно (даже бы я сказал нужно) использовать алгоритм А*, а за эвристическию функцию можно взять манхеттенское расстояние от коня до конечной клетки
Не знал что у єтого есть название, но решал бы тоже "через растояние" и ходы, которые его сокращают
Кстати, не уверен, что А* сработает в данном случае, так как алгоритм выберет самую ближайшую клетку к конечной клетке, но так как конь ходит буквой Г он же может крутиться несколько раз вокруг конечной клетки что бы в неё попасть. А соседняя клетка (которая будет иметь большее манхэтоновское расстояние) попадёт в конечную клетку раньше, хоть эвристика в ней изначально была больше. Я не ради прикопаться, мне тоже сразу в голову пришёл этот алгоритм, просто интересно так это или нет.
@@user-dz1tp4fe4dконь бы не крутился вокруг цели. Он бы просто игнорировал уже пройденные ( найденые ходы ). Если с первой попытки он был не нашел путь, то начал бы обходить ближайшие. Но даже так это было бы куда эффективнее по памяти, чем делать поиск в ширину, так как мы не хранили бы явно плохие ходы
Лучший мотиватор!
спасибо за видео
Привет! Заметил пару неточностей.
1. Ты говоришь, что не посещаешь уже посещенные клетки. Но это утверждение верно только для предыдущего слоя - в коде ты никак не помечаешь те клетки, что были посещены ещё раньше.
2. Формально это можно назвать обходом графа в ширину, но мне кажется, это решение методом динамического программирования. А если попытаться оптимизироавть решение и не проверять заведомо более длинные пути (а ограничиться только квадратом (0, 0) (n, n)), то это уже точно не будет обходом графа в ширину(так как мы не посещаем все вершины).
3. Решение данной конкретной задачи обходом графа в ширину довольно неэффективно - сложность получается ~(2n)^2*Log(n), тогда как методом динамического программирования мы можем обойтись n^2, перебрав каждую вершину урезанного квадрата лишь единожды. n это большая по модулю координата целевой точки.
Upd: попытавшись набросать решение методом динамического программирования, понял, что у меня не получается) Конь ходит слишком сложно, чтобы за один проход можно было заполнить массив, не возвращаясь к уже посещённым клеткам. А вот в обходе графа ограничить поле всё равно было бы нелишним.
так может обозначишь их?
Если входной массив можно редактировать, то одной из оптимизаций будет простая "покраска" значения
> если попытаться оптимизироавть решение и не проверять заведомо более длинные пути (а ограничиться только квадратом (0, 0) (n, n)), то это...
....не будет работать. Например конь (0,0) выход (1,1)
А вообще, мне кажется тут есть математическое решение.
1) В этом и суть решения - можно проверять только предыдущий слой, нельзя попытаться пойти из слоя №3 НЕ в предыдущий слой №2 или следующий слой №4 (иначе бы слои формировались по-другому), поэтому не имеет смысла проверять все посещенные вершины, а только посещенные на последнем слое. Как раз таки поэтому это алгоритм обхода в глубину на двух списках (более классическое решение - одна очередь).
2) Метод BFS (Breadth-first search) как ни странно использует идею динамического программирования. Одно использует, а не заменяет другое. Вы ведь не скажете "Ну я бы не стал доезжать на работу на Мерседесе, я бы предпочел просто доехать на машине." Поиск в ширину реализуется на динамическом программировании. Посещать не все вершины - не значит не обходить граф, но оптимизации действительно здесь приемлемы (можете еще почитать про итеративный поиск в глубину iterative deepening depth-first search).
3) Тут используем хеш таблицу, а не дерево поиска, поэтому время работы алгоритма O(n^2). Но вы все еще правы, что BFS реализуется через идею динамического программирования, просто обход ячеек при рекурентном пересчете соответствует обходу графа.
@@Arkham_nine хорошо, считаем до [n + 2, n + 2] :)
Спасибо!
Альманах...круто, мне нравится
Хорошая задачка, но мне больше интересно как анимация делалась :)
Спасибо за bfs!
Но в аналитическом решении сложность О(1).
N = (lnl + lml)/3 ± 4. Начальные координаты коня (0,0), конечные (n, m). Если рассмотреть как ходить в конце (варианты), то формула будет без погрешностей.
Делай, пожалуйста, больше видео по алгоритмам
Тут экспоненциальный рост клеток с каждым слоем и симметрия 4-го порядка, стоила взять координаты цели по модулю и начать с двух ходов 1, 2 и 2, 1 на первом слое. Так-же можно игнорировать все клетки с отрицательными координатами, это сэкономит память.
Спасибо
Можно ещё параллельно вычислять дорогу от коня к точке и от точки к коню ровно до тех пор покуда не найдётся первое пересечение. Действий суммарно будет больше, но зато массив будет меньше...хотел сказать я, но потом обнаружил одно геометрическое свойство: сумма длин окружностей, пересекающихся в одной точке равна длине окружности с радиусом, равным расстоянию между центрами этих окружностей)))
Вообще в классическом БФС используется очередь (Queue), а не некие уровни.
1. Запихиваешь в очередь первую клетку.
2. Извлекаешь.
3. Находишь всех соседей, в нашем случае восемь возможных ходов коня.
4. Фильтруешь уже посещённые.
5. Запихиваешь в очередь.
6. Гото 2 до победы.
Если смотреть только на previous_layer, то потеряется информация о посещённых клетках на предыдущих ходах.
Уровень в данном случае это синоним глубины. Какие к этому могут быть претензии?
@@rasimbot ну bfs как будто именно для поиска путей используется, а не расстояний, хотя его и можно упростить до поиска минимального расстояния. + как и сказано в видосе, bfs запускается на графе, хоть шахматная доска и представима в виде графа, сам граф в этом решении не строится и вряд ли можно говорить о bfs, хотя и оч похоже. Например, если эту задачку чуть изменить и просить искать не кратчайшее расстояние, а кратчайший путь (именно вывести все посещенные клетки по порядку), то решение из видоса как будто не позволит этого сделать, с bfs получилось бы (ну мне так кажется). Я не с целью надушнить, если что, если это решение без построение графа можно под вышеописанную задачу изменить, буду рад услышать)
@@user-nc6ue1ve3u учи теорию графов лучше)
@@vanel9933 так а что учить то подскажи)
Решение автора работает похоже на работу ИИ, он также связывает всё послойно, и между всеми элементами одного слоя и другого присутствует связь, таким образом происходит имитация синапсов, что помогает ему осмыслить любые возможные варианты.
Видосы у тебя всегда классыные, и объясняешь хорошо, побольше бы. По самому алгоритму. Слишком ресурсоемко обходить все клетки, особенно для большого поля, например, если выход стоит в 50,50 зачем нам идти в минус? а там будет обход и просчет лишних тысяч вариантов, а если доска 100тыс на 100тыс ? Как-то слишком в лоб, можно оптимизировать, тем более, что мы знаем, что конь всегда сдвигается на 2 и 1 клетку, можно заранее проложить маршрут в направлении выхода, а потом при приближении уже перебирать варианты. Конечно, код будет сложнее, но все зависит от задачи, надо экономить ресурсы или нет.
у меня в школе была задача посчитать за какое минимальное число шагов конь пройдет по каждой клетке поля по 1 разу. И всё это на паскале с отрисовкой доски и прочего)
Анимация огонь ))
Но задается вопрос, т.к. мы знаем паттерн движения коня, то почему не исключить несонаправленные вектора для, новых точек и вектора старта и финиша ?
Добрый день, Александр, отличное видео! Вы устраивались на Junior Software Engineer, я правильно понимаю?
Сразу в голову пришла идея через обход в ширину как только сказал про хеш-таблицу ( чтобы в ней хранить позиции, в которых мы были ). На код варсе это 3-4 тир задач.
Так, если координаты конечной точки известны, то может можно искать только в направлении заданой четверти, чтобы не перебирать 3/4 заведомо не нужных направлений?
Сначала конь на клетке 1:1 (зачем-то), потом уже на логичной 0:0. Ну и можно оптимизировать конкретный кейс с учетом осей симметрии доски и обработать только 1/8 всех клеток.
Четко
Для ускорения можно было бы запустить два поиска в ширину одновременно, тогда бы мы могли сократить лишние переборы путей в других направлениях.
в случае коня есть много места для эвристической оптимизации BFS, чтобы не идти в заведомо ложном направлении
Во-первых нормализовать данные. Стартовая клетка пусть будет (0,0), а координаты цели во-первых возьмем по модулю, что не изменит количество шагов, а перенесет цель в верхний правый квадрант заеркально осей, и затем если Х > Y поменяем их местами, чтобы поместить цель выше диагонали (0,0) - (N,N). Для квадрата 5х5 проще всего создать хэш-таблицу, выйдет всего 14 элементов. Если цель дальше 5 клеток то "прыгаем" к ней двигая доску, или вычитая (2,1) из координат цели, добавляя к счетчику 1. Если на очередной итерации цель ушла левее оси Y (отрицательный X), либо "упала" под диагональ (Y < X), то вычитаем не (2,1), а либо (2, -1), либо (1, 2) соответственно. Физический смысл легко увидеть если нарисовать каждую из ситуаций. Как только на очередной итерации мы попали в квадрат 5х5 к цели, снова нормализуем координаты и берем значение из таблицы, добавляем к счетчику итераций и получаем итоговое.
Некрасивая таблица из 14 значений с лихвой компенсируется сложностью О(n) и нулевым выделением памяти на каждой итерации. Описывать сложнее, чем написать код.
Я тоже так решил. Я бы взял разность между координатами по модулю и вычитал (2, 1), (1, 2), пока это возможно, а затем конь либо достигнет цели, либо доберется до любой клетки рядом за 2 хода.
Хм. Зачем там хеш-таблица, если проще и быстрее использовать, например, очередь? Я в обходе в ширину обычно просто добавляю в конец очереди новые вершины-кандидаты на обход. Вершины (в данной задаче клетки), которые уже обошли, хранить в отдельной структуре (в данной задаче я бы использовал двумерный массив, но можно и хеш-таблицу).
У меня 4 года опыта в программировании, 3 года коммерции, чувствую себя таким джуном) Старший разработчик - джун.
Вычисляем первый круг, а дальше копипастим весь массив с наложением в нужную сторону.
Если требуется заполнение всей доски или идет непопадание, возможен банальный брутфорс,
либо от последней позиции, либо вообще всех возможных комбинаций массива.
я бы решал это волновым алгоритмом (алгоритм Ли) без той части где путь восстанавливается. моё решение может быть чуть хуже по памяти, потому что нужно было бы создать двумерный массив с запасом по три клетки от каждой координаты старта и финиша. за то весьма наглядно бы получилось)) номер фронта волны который запишется в ячейку с координатами финиша и будет ответом
Обычная задача на волновой алгоритм. По предоставленному решению. Нет контроля выхода за границу доски. Также проверяем попадание в клетку на предыдущем уровне, но не на уровнях ранее, для данного контроля можно использовать обычный двумерный массив описывающий доску и хранящий уровни посещения в каждой клетке
Шахматное поле предполагается бесконечным?
Can we see the same BFS done recursively ? Would it be an easier way to implement if you have just 15 minutes?
Если наше поле заранее известного размера, то надо использовать обычный массив, а не хеш таблицы. И второе, поиск в ширину выглядит красиво, когда наша цель находиться в нескольких шагах, а когда до неё шагов 30, то мы умрём прежде чем поиск в ширину найдёт путь.
задача - проверить понимание поиска в ширину.. дальше на интервью можно было бы спросить "а давай оптимизируем?"
через 3 недели у меня тоже собеседование в амазон. в алгоритмах я слаб и учу их практически с нуля.
прежде чем посмотреть видео, поставил его на паузу и попробовал решить задачку сам. получилось решить ее за 5 минут. попадется ли мне подобная задача на собеседовании, это уже как повезет.
un canal ruso que encontré para aprender estructura de datos muy buen canal
Стоит ли идти учиться на программиста если уже одну профессию закончил но она мне не нравится? Мне уже 23 года - стоит ли рисковать и переучиваться на программиста?
главное чтоб нравилась профессия
А входит ли в условие задачи память? Ведь алгоритм не слабо так сжирает память
Мне в голову dict пришёл. Можно ли это реализовать, если layer_number - ключ, а сет таплов(или списков) с доступными координатами - значение?
конь на нулевых кордах, мы просто берем число координат, до которых нам нужно дойти и переводим их в положит число, например дали -2 -7, то это считаем как 2 и 7, если -2 7, то 2 7 и тд. берем эти х и у, отнимаем максимальное количество 3 1, 1 3, 6 0 и 0 6 (последняя пара дает sum+=2, первая sum++) до того момента, пока х
Ничего не понятно из твоего объяснения
Ееее Саша видос запилил ща смотреть буду
спс. намешалo бы добавить анализ сложности (временной и по памяти)
функция moves более надежно но абсолютно нечитабельно записывается в данном виде:
from itertools import permutations, product
return [tuple(em * es for em, es in zip(m,s)) for m, s in product(permutations([1, 2]), product(*permutations([1, -1])))]
по-моему, вот ЭТО более нечитабельно. Функция moves выглядит куда проще и нагляднее
@@1001bit ну да, я и написал, что хардкод в данном случае читабельнее. просто показал, как в Питоне выражается "по одной оси на два, по другой -- на один во всех возможный направлениях" посредством функций из itertools
Легенда вернулась, увидимся через год?)
я бы решал через алгебру, но нужно обработать крайние случаи и написать костыли. А так если люди не против и нужно что-то сделать за короткое время то и так можно.
1. Полный перебор не нужен - можно оптимизировать:
1.1. если исходная клетка X
Можно слоями, а можно просто назначить вес каждой клетке.
Хорошее решение. Мысленно представил как решать это на C++, но на Питоне, конечно, компактнее получается решение. Единственный неявный для меня момент алгоритма - это то, что запоминается только предыдущий и текущий слои. Видимо, подразумевается, что с более старыми слоями пересечения быть не может. Приму на веру, видимо, есть строгое доказательство данного факта.
Если граф двунаправленный, то предыдущий слой это заслонка для всех возможных путей обхода. Можешь представить длинный коридор с дверьми, где ты захлопываешь за собой дверь, но предпредыдущая всегда открывается после этого. Но до нее ты не дойдешь, т.к. уже захлопнул дверь, которая ведет к ней.
@@Abingususчто такое «двунаправленный граф»? Я знаю только неориентированные и ориентированные графы. Я не понял, как ваш комментарий относится к тому, что я написал выше. В теории конь не обязан не возвращаться к клеткам из более старых слоев.
когда лет 20-25 назад делал игру Lines на дельфи аналогично просчитывал путь для шарика из исходной точки в точку в которую кликнул игрок
Что мне нужно делать, что бы понимать о чем ты вообще говоришь)) Я вообще не улавливаю, что нужно изучать в самом начале ? Я хочу знать, но полагаю нужно дойти до этого, а что бы дойти, нужно с чего то начать, скажи с чего начать, если я даже не понимаю о чем ты говоришь :DDD
А теперь попробуйте решить ту же задачу, но слегка сложней:
Есть вместо одного k коней на поле. Нужно для каждой клетки поля понять за какое минимальное количество ходов один из этих коней доберется до нее
Здравствуйте, Александр, а Лукин Владимир Николаевич не ваш родственник (в маи преподаёт) ?
Спасибо!
1. хотелось бы в коде видеть номера строк, чтобы ссылаться на них в комментах
2. не увидел ограничения доски, возможно мне стоит самому реализовать, но кажется, находясь в x=2 y=1 мы выскочим за пределы доски.
3. не увидел где инициализируются x, y, возможно это особенность, или просто опустили из примера.
4. что если выход будет в [-1, -1] ?
про доску в начале объяснялось, про то, что она бесконечная не сказано, но обрати внимание на координаты. Если [1,1] Это стартовая позиция
@@kotiko_oksвидимо нужно самому реализовать с тестами)
2. Ограничение не нужно в контексте задачи. Ограничения доски представлены максимальным и минимальным значением типа int в python
3. (x, y) - это итератор в цикле for, который там же инициализируется
"for (x, y) in layer" перебирает все пары (кортежи) (x, y), которые находятся в layer
4. Даже чисто математически не имеет значения, если выход находится на отрицательных координатах
@@1001bit 2-3 понял, питон не знаю просто. 4 суть не в отрицательных координатах, а в том, что ограничения доски я не видел, поэтому решил, что конь просто уйдёт за пределы и никогда не вернётся в -1,-1.
Не,вообще транзитивное замыкание с минимальным весом штука крутая и очень мощная,но тут явно можно докрутить из-за специфики задачи.
Скажем,вот у нас две точки,которые надо соединить и они образуют как бы прямоугольник и вот выясняется,что если его немного расширить,то любой минимальный путь можно перестроить без потерь так,чтобы он в прямоугольник попал.
Для удобства перекрутим так всё,чтобы вход был слева снизу и выход справа сверху.
Понятно,что на ответ это не повлияет,а вот на ход решения повлияет сжатием бреда.
Докажем это замысловатое (или не особо) утверждение:
Пускай есть какой-то путь и он неуменьшаем.Тогда все точки,которые выходят за верхнее ограничение мы отразим зеркально вниз,если есть такие две точки,что она на одном уровне.Понятно,что такое преобразование не изменит длинну пути,но применив так много раз потом мы запихаем весь путь в рамки наши.Проблема в том,что они могут быть на разных уровнях,так как по осям у нас переход на 2 или на 1.
В этом случае придётся воспользоваться оптимальностью пути.
посмотрим на кусок пути,где вот он начал уходить вверх за границу и в какой-то момент вернулся в в прямоугольник,но на уровень ниже (выше нельзя,так как там кончается граница).Тогда давайте заметим такой факт,что нам важно то именно с точки зрения конца пути чтобы всё было хорошо,а на остальное пофигу.Тогда отразим весь этот подпуть относительно горизонтали,проходящей через конец пути.В случае,если начало проблемного подпути было на одной высоте с точкой выхода проблем не будет,но вот если она была ниже на один,придётся ещё подумать.
Итак,у нас плохой кусок пути начинается за 1 единицу до конца и заканчивается прямо на конце.Другие случаи мы уже разобрали,этот-последний.
Тут прям нетривиально!
Рассмотрим последние два действия.
У нас проблемы из-за того,что последний ход был на 2 шага по высоте,иначе бы мы нашли что отразить.
Так же первый шаг не был по высоте на 1,так как иначе после отражения мы посмотрим на 1 шаг до конца и сможем на изи отразить.
Те первый и последний прыжки были на 2 вверх и вниз.
Однако раз у нас не совпали высоты,применили прыжок по высоте на 1 нечётное число раз и хотя бы 1 раз.
А что,если его убрать и вставить как нам надо?
Тогда мы закончим на 2 клетку по иксу куда-то не туда и на 1 клетки по y куда-то не туда.
рассмотрим все случаи:(+-2;+1)
Тут просто,по иксу понятно что на 2 в нужную сторону догонимся и по игреку как раз одной хватит.
Но что,если (+-2;-1),ведь тогда нам надо уже на 3 двигаться.Надо это как-то проработать.
Тут просто на самом деле.В каком-то из ходов,где высота по 2 меняем сторону по высоте (как минимум,начало и конец с разными знаками и можно выбрать кандидата (последний после переворота перевернём и кайф)).
Так же делаем по иксу хитрость нашу,когда слишком вправо.
Влева и вниз - ну просто думаем,что путь шёл с конца на начало и наши рассуждения все.
Тут важно,что при любом из описанных действий нехороший кусок теряем как минимум два звена в себе (они становятся хорошими) и конечным количеством таких действий получится всё запихать в коробку.
Но какая же коробка?
Как минимум,надо по каждой оси чтобы было длинна коробки 4,иначе не проходит наше приведение.
Ведь в худшем случае мы сдвигались на 1,при этом замутив крутой перекрут,юзавший ещё 3 ниже.
А лучшие вообще ничего не делали плохого:самое жёсткое-это на две спускались,чтобы плохой кусок уменишить.
Те min{4;|start'-finish'|} по каждой оси.
Ну или,если мы как-то узнали,что в пути нет последнего стрёмного варианта (мало ли),то min{3;|start'-finish'|}.
Если что,это расстояние от начала и конца до противоположных стенок.Если не хватит,то увеличивать СО ВСЕХ СТОРОН!
Теперь с чистой совестью можно урезать поле,зная,что все пути будут (хоть и перекрученные) найдены и замыкание именно для последней вершины будет таким же.
Тут,конечно,важно,что для других вершин это будет не так (хотя,нам какая разница).
Заметим,что такая оптимизация хоть и сложна в понимании,проста в реализации и при том очень эффективна.
Я так понимаю, доска задачи бесконечная? Функция moves не смотрит на границы доски.
а почему не проверяем x и y плюсовый или минусовый ? если плюсовый то например -x не нужно посмотреть
Но почему (1; 1), а не (0; 0), Карл?
Знаю 2 решения:
1. За O(1) можно пересчитать по формуле, опирающиюся на полуинвариант сумм
2. BFS или Дейкстра, оба за O(n) в данном случае
А можно ссылку на объяснение первого решения? Или просто объяснить поподробнее)
Поле a1 в шахматах черного цвета)
Можно добавить эвристическую функцию и получить AStar (будет быстрее)
решение не лучшее, но сойдет. особенно для джуна.😁
ну шахматная доска это матрица. это раз.
врытое уже зависит что именно надо! просчитать ходы - это граф. узнать где какая фигура - это матрица.
третье, структуры данных все же стоит подтянуть.😁
Считаем разницу по оси X и Y между текущим положением коня и нужной клеткой, получим Sx и Sy. Если Sx и Sy кратны 3, то количество ходов = (Sx + Sy)/3.
В противном случае if Sx>5 then Sx_first = round((Sx-3)/3, 0); Sx_last = Sx - Sx_first*3 else Sx_first = 0; Sx_last = Sx, то же для Sy, Sу_first, Sy_last.
Sx_first + Sу_first - количество ходов, что бы оказать в окрестности Sx_last, Sy_last клетки, не более 5 клеток. И вот тут можно применить какой угодно алгоритм.
В чём преимущество, если доска 1000^1000 на 1000^1000, то со слоями может быть проблема, а так нет.
у меня была такая задача но шахматная доска 1000 на 1000 и оно работает долго че делать?
Неужели там не появляется паттерн, чтобы можно было написать формулы, в которые можно подставить исходную и целевую координаты и сразу получить ответ, по крайне мере для ситуаций, когда исходная и целевые поля не у края доски?
Можно за линейную, написал коммень, но кажется можно за консьантную сложность
О(n)^2 очень високая сложность. Можно ли сделать бистрее?
Из-за двух циклов for?
Да ну нах..лучше в таксисты пойду.
Какие 7.5к € джуниору в Германии?; 90к в год даже техлиды не все получают. В 4к брутто - поверю, если данные есть: законченый универ, например, с дуальным обучением.
Алгоритм Дейкстры
Это же по сути полный перебор, а значит алгоритм не эффективный.
Можно изучить свойства движения коня и вывести некую формулу. Типа идем на прямую к целевой клетке, пока она не попадет в заранее просчитанный квадрат 5*5. Возможно, можно просто формулу вывести четкую
Что-то простенькая довольно задача и данное решение
Задача решается поиском в ширину. Решал аналогичную задачу в универе на экзамене по АСД (Алгоритмы и структуры данных) на третьем курсе
Я бы решал через вектор до выхода - т.е. какой из возможных ходов сокращаяет дистанцию до выхода
А это язык программирования пайтон ?
Да
а нет названия у данного алгоритма? я так понял что это не типовой алгоритм
BFS
КрасавчеГ!!!
А пузырьковый метод не сработал бы?
Я бы решал через граф, похожая задача была на лекциях у Тимофея Хирьянова, соответственно граф бы представлял из себя словарь с вершинами и множеством соседних вершин
Если посмотреть видео, то автор собственно и сказал, что шахматная доска представляет из себя граф, и он будет решать через поиск в ширину.