Самый короткий путь (матрица)

486 просмотра
0
0 Комментариев

Да, матрица, не дерево, т.е. Дейскра тут не катит.

Есть матрица 1000х1000, а вообще она произвольная. Пусть будут координаты 134х444 и 751х199. Собственно как найти между ними самый короткий путь, сколько нужно пройти ячеек между ними.

Язык С++, а лучше python. Хотя мне все равно какой 🙂 Спасибо.


Добавить комментарий

2 Answers

Python Опубликовано 09.12.2018
0

Мне по душе c#, на примере сделай 🙂

int[] a = {134, 444};
int[] b = {751, 199};
int s = 0;
 
while (a != b) {
    if ((a[0] < b[0]) && (a[1] < b[1])) { a[0]++; a[1]++; }
    else if ((a[0] < b[0]) && (a[1] > b[1])) { a[0]++; a[1]--; }
    else if ((a[0] > b[0]) && (a[1] < b[1])) { a[0]--; a[1]++; }
    else if ((a[0] = b[0]) && (a[1] < b[1])) a[1]++;
    else if ((a[0] = b[0]) && (a[1] > b[1])) a[1]--;
    else if ((a[0] < b[0]) && (a[1] = b[1])) a[0]++;
    else if ((a[0] > b[0]) && (a[1] = b[1])) a[0]--;
    s++;
}
 
Console.WriteLine(s.toString());

Добавить комментарий
0

Вы действительно описали задачу неполно. Предположим, что переход по горизонтали равноценен переходу по вертикали. Тогда возможны два варианта.

Переход по диагонали неразрешен. Тогда минимально возможная длина пути расчитывается как сумма длин сторон прямоугольника, на которых расположены точки

def min_way(x1, y1, x2, y2):
    return abs(x2-x1)+abs(y2-y1)

Переход по диагонали разрешен и равноценен переходу по вертикали/горизонтали. Тогда минимальный путь равен длине максимальной стороны

def min_way(x1, y1, x2, y2):
    return max(abs(x2-x1), abs(y2-y1))

Добавить комментарий
Напишите свой ответ на данный вопрос.
Scroll Up