Помогите решить задачу

← →
Delphin © (2005-01-26 19:30) [0]

Уже 3 часа пытаюсь её решить, всё никак не могу додуматься;(
Дана прямоугольная клеточная доска n*m клеток. В левой нижней клетке (1,1) находится шахматный конь.
Шахматный конь может перемещаться по шахматным правилам (либо на одну клетку по вертикали и 2 по горизонтали, или 2 по вертикали и одну по горизонтали)
Так, например, если n=4, m=3 и конь находится в клетке (2,1), тогда следующим ходом он может переместится только на одну из следующих клеток (1,3), (3,3), (4,2).
По введённым значениям натуральных чисел n,m,i,j (n<=100, m<=100, i<=n, j<=m) определить и вывести, какое минимальное количество ходов конём необходимо сделать, чтобы из клетки (1,1) перейти в клетку с координатами (i,j). Если в клетку перейти нельзя, то вывести сообщение с текстом "No variants"

Заранее благодарен

← →
TUser © (2005-01-26 19:48) [1]

Почитай про динамическое программирование. А также про алгоритм Дейкстры. А в принцыпе - задача классическая, наверняка в сети решений море.

← →
pasha_golub © (2005-01-26 19:50) [2]

TUser © (26.01.05 19:48) [1]
А также про алгоритм Дейкстры.

Какой именно алгоритм имеется ввиду?

← →
TUser © (2005-01-26 19:52) [3]

Алгоритм поиска минимального пути в графе. А что есть другие алгоритмы названные его именем (действительно интересно)?

← →
Delphin © (2005-01-26 19:55) [4]

кое-что я уже откопал: http://algolist.manual.ru/maths/combinat/knight.php :))
TUser © (26.01.05 19:52) [3]
Уже ещу

← →
wicked © (2005-01-26 20:06) [5]

> Алгоритм поиска минимального пути в графе. А что есть другие
> алгоритмы названные его именем (действительно интересно)?

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

в Мир ПК за январь 2003 года вроде была статья Н.Шамгунова по сабжу

TUser © (26.01.05 19:52) [3]
Да, как оказалось есть и другие. Я сам был удивлен, потому как знал только про минимальное расстояние.

Но, ИМХО, к этой задаче этот алгоритм не применить.
Тут даже матрицу инцидентности не построить...

> Но, ИМХО, к этой задаче этот алгоритм не применить.
> Тут даже матрицу инцидентности не построить...
Не знаю, что такое матрица инцедентности. Но вроде все понятно - есть граф, вершинами которого являются клетки доски, и две вершины соединены ребром тогда и только тогда, если возможно попасть за один ход из одной в другую. Найти минимальный путь из вершины А в вершину Б. Задача решается алгоритмом Дейкстры.

Помогите решить задачу Найти похожие ветки