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

Question

[Sylvester_Stallone]

Дана строка:

+----------------0---------------+
|                                |
|                                |
|          Y        D            |
|     A                          |
|              E                 |
|           N                    |
|  Y                             1
3        Y    D                  |
|         A              X       |
|                                |
+----------------2---------------+

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

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

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

Да да, не удивляйтесь. это действительно задача на javascript, вообще не понимаю как "подступиться" к этой задаче.
Через какой алгоритм ее решать, или знания в какой сфере javascript необходимы, чтобы ее решить?!

Comments

[Сергей Соколов]

1 ход – только влево-вправо-вверх-вниз, или по диагонали тоже можно?

[Сергей Соколов]

«расстояние» от буквы до цифр считать как целое мин. число шагов, или необязательно целое по прямой?

[Slavik KENNY]

Буква приближается к цифре на одну клетку за одну секунду.

К какой цифре? Ближайшей, самой дальней, каждая буква к своей? В условии ни слова о том, куда вообще какая буква стремится.

Answer 1

[Rsa97]

Всё, что нужно для решения данной задачи - знание основ какого-либо языка программирования и умение декомпозировать задачу на тривиальные подзадачи..
В целом, алгоритм разбивается на три подзадачи:
- найти координаты всех букв и цифр;
- для каждой буквы найти расстояние до ближайшей цифры;
- найти максимум из этих расстояний.
Для решения второй подзадачи нужно знать правила движения букв - только по одной координате за раз или допускается движение по обоим координатам одновременно.

Comments

[Sylvester_Stallone]

А как в JavaScript реализовать вот это "- для каждой буквы найти расстояние до ближайшей цифры;"

[Rsa97]

Sylvester_Stallone, А вот для этого и надо знать, как именно движется буква. Вы назвали скорость движения, но не назвали правила. Если буква стоит в координатах (5, 5), то может она сдвинуться сразу в (6, 6) или только в (5, 6) или (6, 5)?

[kalapanga]

И ещё:
1) Могут ли в одной клетке оказаться одновременно несколько букв? Не в начальной позиции, а в процессе?
2) Что обозначает само "буквы приблизятся к цифре"? (Вопрос этот связан с первым) Все буквы двигающиеся к одной цифре должны оказаться в клетке с координатами этой цифры? Или они будут скучиваться вокруг, в соседних клетках?

[Wataru]

Sylvester_Stallone, если вы уже знаете координаты - то надо для каждой буквы уиклом пройтись по каждой цифре, посчитать расстояние и взять минимум. Для подсчета рачстояния нужна формула. Или |x1-x2|+|y1-y2|. Или максимум из двух разностей, если модно двигаться и по диагонали.

[Sylvester_Stallone]

kalapanga,
2) Все буквы двигающиеся к одной цифре должны оказаться в клетке с координатами этой цифры?
- ДА!

Answer 2

[Alexandroppolus]

если букв и особенно цифр очень много, то можно оптимизировать:
1) Для каждой стороны получить массив точек с цифрами и отсортировать по расстоянию от левого края или от верха.
2) Далее для каждой буквы проверять каждую из 4 сторон. При проверке стороны находить на этой стороне цифру, ближайшую к букве, например двоичным поиском, и уже смотреть расстояние до этой цифры. Далее сравнивать результаты для каждой из сторон, выбирать минимум.

Comments

[Wataru]

Еще один метод - запустить обход в ширину от всех цифр. Потом для каждой буквы посмотреть а какое же расстояние клетка под ней имеет после обхода.

В случае, когда поле сильно заполнено - это будет O(n^2) вместо O(n^2 log n) у вас.
Т.е. у вас метод быстрее в среднем, но вот это - быстрее в худшем случае.

[Alexandroppolus]

Wataru, да, точно. Это сработает, если нам нужно "поклеточное" расстояние. Я почему-то думал, что требуется расстояние по прямой, но скорость "1 клетка в секунду" всё-таки намекает на перемещение по клеткам..