На Pascal'е:

Помогите пожалуйста решить такую задачу:
Дана квадратная матрица NxN.

A11 A12 … A1n
A21 A22 … A2n
…………
An1 An2 … Ann

Нужно найти кратчайший путь из A11 в Ann при условии, что переходить можно только на элемент, который больше или равен настоящему. Двигаться можно во всех направлениях (в т.ч. и по диагонали).

Никак не могу придумать сам алгоритм поиска пути. Хотя бы в какую сторону копать?
Буду очень признателен…

Здравствуйте, vovik777, Вы писали:

V>На Pascal'е:

V>Помогите пожалуйста решить такую задачу:
V>Дана квадратная матрица NxN.

V>A11 A12 … A1n
V>A21 A22 … A2n
V>…………
V>An1 An2 … Ann

V>Нужно найти кратчайший путь из A11 в Ann при условии, что переходить можно только на элемент, который больше или равен настоящему. Двигаться можно во всех направлениях (в т.ч. и по диагонали).

V>Никак не могу придумать сам алгоритм поиска пути. Хотя бы в какую сторону копать?
V>Буду очень признателен…

Обход в ширину.

Здравствуйте, vovik777, Вы писали:

Динамическое программирование.

Вкратце:
Если кратчайший путь до вершины a[i,j] обозначить как path(i,j) а расстояние между верщинами a[i,j] и a[k,l] как dist(i,j,k,l)

то

path(i,j) = min(path(i - 1,j) + dist(i - 1, j, i, j), path(i,j - 1) + dist(i, j - 1, i, j), path(i - 1, j - 1) + dist(i - 1, j - 1, i, j))

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

Здравствуйте, vovik777, Вы писали:

V>На Pascal'е:

V>Помогите пожалуйста решить такую задачу:
V>Дана квадратная матрица NxN.

V>A11 A12 … A1n
V>A21 A22 … A2n
V>…………
V>An1 An2 … Ann

V>Нужно найти кратчайший путь из A11 в Ann при условии, что переходить можно только на элемент, который больше или равен настоящему. Двигаться можно во всех направлениях (в т.ч. и по диагонали).

V>Никак не могу придумать сам алгоритм поиска пути. Хотя бы в какую сторону копать?
V>Буду очень признателен…

Например, здесь

Необходимо будет модифицировать.

Алексей.