Найти кратчайший путь коня между двумя заданными клетками

FastCode 29 4

Первая функция размечает доску, вторая рекурсивно перечисляет пути из конечной точки. Разметка идет "по спирали". Номер витка (круга) соответствует минимальному расстоянию от начальной точки. На каждом витке неразмеченные клетки просматриваются в паре с каждой клеткой последнего витка. Если расстояние (сумма квадратов разности координат равно пяти) соответствует шагу коня клетка включается в следующий виток (круг). И так пока в круг не попадет конечная клетка. В каждой клетке запоминается массив клеток предыдущего витка, из которых попадают в текущую. Это дает возможность рекурсивно раскрутить пути до начальной точке "при спуске".

Автор: ildarovich

Функция Спираль(А, Б, Круг = 0)Экспорт
    Поле = НоваяТаблицаЗначений("Х, У, Круг, Связи");
    Для К = 0 По 63 Цикл 
        ЗаполнитьЗначенияСвойств(Поле.Добавить(), Новый Структура("Х, У, Круг, Связи", Цел(К / 8), К % 8, (К = А) - 1, Новый Массив))
    КонецЦикла;
    Пока Поле[Б].Круг < 0 Цикл 
        Целина = Поле.НайтиСтроки(Новый Структура("Круг", -1));
        Трек = Поле.НайтиСтроки(Новый Структура("Круг", Круг));
        Для Каждого С Из Целина Цикл
            Для Каждого К Из Трек Цикл
                Если (С.Х - К.Х) * (С.Х - К.Х) + (С.У - К.У) * (С.У - К.У) = 5 Тогда
                    С.Круг = Круг + 1;
                    С.Связи.Добавить(К.Х * 8 + К.У)
                КонецЕсли
            КонецЦикла
        КонецЦикла;
        Круг = Круг + 1
    КонецЦикла;
    Возврат Поле
КонецФункции
Процедура Спуск(Б, Поле, Знач Путь = "") Экспорт
    Путь = Сред("abcdefgh", Б / 8 + 1, 1) + (Б % 8 + 1) + " " + Путь;
    Если Поле[Б].Связи.Количество() = 0 Тогда
        ЗаполнитьЗначенияСвойств(Пути.Добавить(), Новый Структура("Путь", Путь))
    Иначе
        Для Каждого К Из Поле[Б].Связи Цикл
            Спуск(К, Поле, Путь)
        КонецЦикла
    КонецЕсли
КонецПроцедуры
Орфографическая ошибка в abcdefgh: abcdefgh
TurboConf - расширение Конфигуратора 1С

Похожие публикации

Поиск кратчайших путей по алгоритму Флойда-Уоршолла

Модератору