Методы решения задач типа: ход конем

[Levsha100]

Собственно вопрос- как решать задачи подобного типа?

"На шахматной доске размером m*n клеток несколько клеток вырезано. Провести путь минимальной длины из одной заданной клетки в другую ХОДОМ КОНЯ через не вырезанные клетки"

Мой вариант решения такой: Решаем задачу с помощью теории графов. Представляем каждую клетку поля вершиной неориентированного графа. К одной вершине присоединяем только ту, в которою можно походить конем и если она- не вырезанная клетка.

Есть ли более экономичные/правильные варианты решения?

[Sazary]

Берем исходную клетку и ставим туда 0.
Потом во все доступные с одного хода клетки ставим 1. Дальше для каждой из этих клеток смотрим все доступные и ставим туда 2 (если еще ничего не стоит). И так пока все не заполним. В итоге имеем матрицу, в каждой ячейке которой стоит число - минимальное количество ходов, за которое к ней можно добраться.
Потом берем конечную клетку и от нее идем к начальной. Ну или еще во время заполнения смотреть, не попали ли в конечную клетку.
Как-то так. Называется, вроде, волновой алгоритм.

[Levsha100]

Блин, точно!
Протупил...)
Еще 400 примеров решу и займусь информой.
Sazary, спасибо!
// Кстати, тогда уже можно использовать "двойной" волновой алгоритм, т.е. "трассировать" путь из двух точек одновременно.
///Блин, я тупой, как не мог додуматься раньше...

[Sazary]

Сообщение от Levsha100

// Кстати, тогда уже можно использовать "двойной" волновой алгоритм, т.е. "трассировать" путь из двух точек одновременно.

Мм.. Это как? Ведь изначально вы не знаете, сколько ходов до конечной точки.

[Levsha100]

Эммм... над этим нужно подумать....
Я просто провел аналогию с волновым алгоритмом, тут, наверное, немного другое. Суть в том, что эффективность возрастает в несколько раз при "параллельном" поиске.
Опять, наверное, протупил Неа, после дня решения алгебры/геометрии мне категорически запрещается писать на форуме .
//Что то типа breadth-first vs bidirectional...

[Sazary]

Вообще, этот самый параллельный поиск будет эффективен только если будет осуществляться одновременно. То есть, придется смотреть в сторону многопоточности. Тогда обход от начала может ставить в ячейки положительные значения, а обход от конца - отрицательные. При встрече суммируем по модулю. Ну там еще подумать надо.
В общем, по-моему проще сделать по-обычному ))

[Levsha100]

будет эффективен только если будет осуществляться одновременно

Тут основная суть показываеться, если посмотреть на рисунок:
Хотя да легче сделать более простым способом.

[Sazary]

А что за красная линия? И почему 3 окружности? )
Имел в виду, что если поиск будет выполняться последовательно, пусть даже попеременно из одной точки и из другой, то по скорости это все равно будет также, как и обычный поиск. Вот )

А картинка напоминает какую-то абстрактную композицию

[Levsha100]

Объясняю свой рисунок
Линия это разделитель, верху Ваш вариант, внизу- мой.
Красные точки- начало и финиш(или наоборот, значения не имеет)
Окружности ограничивают пройденные клетки массива.
В Вашем варианте одна окружность, потому что Вы ищете последвательно от
начала до конца. А в моем мы "проходим" клетки "одновременно".
Получается что при одинаковом количестве "ходов" мои окружности ближе друг к другу чем Ваша к финишной точке.
Воть.
Надеюсь Вы хоть что то поняли, ибо я слишком сумбурно объяснил...

[Sazary]

В принципе, понял. И мнение не изменилось - в однопоточной программе выигрыша не будет. Да и потом не совсем ясно, как вы это будете реализовывать )