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

FastCode 1534 13 21 67
1С Минимализмы Задачи

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

Автор: ildarovich

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

См. также

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

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

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

Перенос настроек данных формы между пользователями

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

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

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

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

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

Модератору