Что такое кратчайшее расстояние между двумя узлами в матрице?

Question

У меня есть матрица 5х5 (25 узлов).Есть ли формула, по которой я могу найти кратчайшее расстояние между 2 узлами i и j в матрице?

Примечание: расстояние между 1 узлом и его соседом составляет 1 единицу.

=================

По моим наблюдениям, существует много путей с одинаковым расстоянием между этими двумя узлами i и j, поэтому я не уверен, существует ли формула длярассчитать самый короткий?Я ценю, если кто-нибудь может помочь.Спасибо.

Пример:

* * * i *
* * * * *
* * * * *
* * * * *
* j * * *

Наименьшее расстояние между i и j составляет 6 единиц.

Answer 1

Я считаю, что вам нужно расстояние L1, также называемое Манхэттенское расстояние .Таким образом, если ваши два узла имеют матричные индексы (i1,j1) и (i2,j2), то кратчайшее расстояние между ними равно |i1-i2|+|j1-j2|.

Это, конечно, при условии, что вы не можете двигаться по диагонали.

Answer 2

Взгляните на Метрическое пространство

Answer 3

Я думаю, что нормальная теорема Пифагора будет работать просто отлично.Получите разницу X, Y между тем, где вы находитесь и куда вы хотите пойти;это даст вам отрицательное или положительное значение.Отсюда вы сможете перемещаться вверх / вниз влево / вправо по мере необходимости, пока не окажетесь в той же строке / столбце.Не могу понять, как получить верхний индекс;но это будет работать.

a^2 + b^2 = c^2