Добрый день...
Уважаемые знатоки, помогите пожалуйста, хоть вектором, как реализовать данное тестовое задание?
Поиск кратчайшего пути
Срочная новость! 18 февраля 2021 года марсоход “Персеверанс” прибыл на Марс для
исследования кратера Езеро в рамках миссии НАСА «Марс-2020».
Через несколько дней исследований марсоход провалился сквозь скальную породу внутрь
кратера. Судя по первым снимкам это руины, оставшиеся от древней цивилизации.
Во время падения повредился Радиоизотопный термоэлектрический генератор и
единственным источником энергии остались литий-ионные батареи, которые заряжаются
от солнечной энергии. Но под землёй нет солнечного света. Нужно как можно скорее
выбраться на поверхность.
Марсоход укомплектован отдельным беспилотным летательным аппаратом, оснащённый
камерами ночного видения, с помощью которого он смог получить карту местности и
увидеть выход. Только оказалось что проектировщики марсохода не предусмотрели
алгоритмов поиска пути. А электроэнергии на неоптимальный маршрут может не хватить.
Марсоход использует радиационно устойчивый одноплатный компьютер на базе
процессора RAD750 с частотой 133 МГц и 128 Мбайт динамической памяти и может
запускать программы на языке Java. Инженеры НАСА договорились использовать
интерфейс RouteFinder (описание ниже). Пока они спорят о том какой алгоритм лучше
успей их опередить и написать оптимальный алгоритм и спасти научные исследования
Марса. Вычислительной мощности компьютера марсохода и памяти очень мало,
постарайся учесть это в своей программе.
Торопись, у него осталось совсем немного энергии чтобы выбраться на поверхность!
/**
* Интерфейс поиска маршрута
*/
public interface RouteFinder
{
/**
* Поиск кратчайшего маршрута между двумя точками
* @param map карта
* @return карта с построенным маршрутом
*/
char[][] findRoute(char[][] map);
}
На вход функции findRoute передается двумерный массив размерностью KxL
(1<=K,L<=10000). В качестве элементов данного массива допускаются следующие
символы:
# преграда
. дорога
@ начальная точка
X конечная точка
Допустимо перемещение только на соседние клетки по вертикали и по горизонтали (по
диагонали перемещение недопустимо). В случае, если построение маршрута
невозможно, функция findRoute должна вернуть null. В качестве результата необходимо
получить массив символов с построенным маршрутом. Маршрут прокладывается
символом ‘+’.
Пример 1
Ввод
...@.
.####
.....
####.
.X...
Вывод
+++@.
+####
+++++
####+
.X+++
Пример 2
Ввод
..X..
#####
.....
.@...
.....
Вывод
null
Пример 3
Ввод
....@
#.###
.....
....X
.....
Вывод
.+++@
#+###
.+...
.+++X
.....
Илья
2 уровень
Задание на вакансию стажера, помогите
Комментарии (9)
- популярные
- новые
- старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
wan-derer.ru
13 мая 2021, 12:26
Используй алгоритм "Разбегающаяся волна".
- начальную точку помечаешь "0";
- каждую валидную точку вокруг неё - "1";
- каждую вокруг них - "2";
и т.д.
Очень компактно этот алгоритм выражается с помощью рекурсии.
Как определить что волна дошла до конечной точки (т.е. путь есть) и как найти по значениям кратчайший путь - разберёшься сам :)
Кстати: это один из простых алгоритмов автоматической трассировки печатных плат.
0
Стас Пасинков Software Developer в Zipy Master
11 мая 2021, 19:25
если сам пытаешься придумать алгоритм - это похвально. но тогда напиши свои какие-то идеи хотя бы или наработки.
потому что за тебя никто ничего делать не будет, и логично, что отправят в гугл :)
а вот если помочь - тогда можно, да :)
+1
Justinian Judge в Mega City One Master
11 мая 2021, 12:43
Вектор?
В гугль:
Поиск кратчайшего пути, графы, алгоритм Дейкстры, A стар алгоритм, алгоритм Ли (волновый алгоритм) и тд
+ на гитхабе есть решения этой задачи
+2
Евгений Backend Developer в KHAN Group Expert
12 мая 2021, 13:03
Откуда вы эти штуки знаете? У тебя мат.образование? Вот хотелось бы на самом деле знать это всё, чтобы потом понимать, что искать.
0
Anonymous #2478379
12 мая 2021, 14:48
Хороша документалка в тему алгоритмов.
Там кстати есть отсылка и к данной задаче
https://www.youtube.com/watch?v=OgXQRoPnqeQ
0
Justinian Judge в Mega City One Master
12 мая 2021, 15:00
Это очень базовые понятия и алгоритмы, просто сталкивался с ними когда-то.
В данном конкретном случае это находится в 1 секунде от окошка поиска гугля, вот так ты и поймешь что искать :)
Будет задача, вычленишь суть, введешь в гугль, увидишь вектор - какими алгоритмами решается, примеры решения, а дальше будешь уже углубляться, выберешь один алгоритм снова в гугль, детально почитаешь, посмотришь примеры реализации, разберешь его и напишешь свой вариант реализации.
Поэтому в данном случае, речь о том, что автор вопроса вместо запроса в гугль написал сюда, если бы он погуглил, как я писал, он от конкретных алгоритмов до решений этой задачи нашел бы, причем за считанные секунды.
+1
Евгений Backend Developer в KHAN Group Expert
12 мая 2021, 16:36
Это да. Ну всё равно сразу знать куда копать так то лучше:)
0
Стас Пасинков Software Developer в Zipy Master
12 мая 2021, 20:24
ну это просто опыт :)
никто не знал о существовании алгоритма Дейкстры с рождения :)
просто в какой-то момент узнаешь об этом, вот и все :)
0
Влад Java Developer в Tinkoff
12 мая 2021, 22:44
https://www.youtube.com/watch?v=7oUt0zhv2sA&ab_channel=QWERTY
0