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

FastCode 1384 11 21 66

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

Автор: ildarovich

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

Рекомендации

См. также

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

ВыполнитьОбменДанными (БСП)

ПутьКТабличнойЧасти (БСП)

НайтиВРегистреПоПути (БСП)

НайтиЭлементыИГруппыОтбора (БСП)

ТекстЗапросаВыбораИзменений (БСП)

НайтиСтрокуВДанныхФормыДерево (БСП)

НайтиВариантыОтчетов (БСП)

НайтиЭлементОтбораПоПредставлению (БСП)

Обновлятор-1С: групповое (пакетное) обновление и обслуживание всех баз за один раз

Комментарии

Модератору