@Sylvester_Stallone

Как решить задачу на алгоритмы?

Дана строка:
+----------------0---------------+
|                                |
|                                |
|          Y        D            |
|     A                          |
|              E                 |
|           N                    |
|  Y                             1
3        Y    D                  |
|         A              X       |
|                                |
+----------------2---------------+


За сколько секунд все буквы приблизятся к цифрам

Считается, что:

Буква приближается к цифре на одну клетку за одну секунду.
Буквы никак не взаимодействуют между собой.
Если расстояние от буквы до нескольких цифр одинаковое, то буква приближает к цифре с минимальным значением.
Каждая цифра уникальная (не повторяются).
Цифр на одной стороне может быть несколько, но у всех уникальные координаты.
Строка - прямоугольник.

Да да, не удивляйтесь. это действительно задача на javascript, вообще не понимаю как "подступиться" к этой задаче.
Через какой алгоритм ее решать, или знания в какой сфере javascript необходимы, чтобы ее решить?!
  • Вопрос задан
  • 179 просмотров
Пригласить эксперта
Ответы на вопрос 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Всё, что нужно для решения данной задачи - знание основ какого-либо языка программирования и умение декомпозировать задачу на тривиальные подзадачи..
В целом, алгоритм разбивается на три подзадачи:
- найти координаты всех букв и цифр;
- для каждой буквы найти расстояние до ближайшей цифры;
- найти максимум из этих расстояний.
Для решения второй подзадачи нужно знать правила движения букв - только по одной координате за раз или допускается движение по обоим координатам одновременно.
Ответ написан
Alexandroppolus
@Alexandroppolus
кодир
если букв и особенно цифр очень много, то можно оптимизировать:
1) Для каждой стороны получить массив точек с цифрами и отсортировать по расстоянию от левого края или от верха.
2) Далее для каждой буквы проверять каждую из 4 сторон. При проверке стороны находить на этой стороне цифру, ближайшую к букве, например двоичным поиском, и уже смотреть расстояние до этой цифры. Далее сравнивать результаты для каждой из сторон, выбирать минимум.
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы