|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 23 Nov 2001 12:25:55
To : desyatnik@dax.ru
Subject : Re: Интересная задача
--------------------------------------------------------------------------------
Привет! "Alexey Desyatnik" <desyatnik@dax.ru> сообщил(а) нам:
> Дана шахматная доска NxN (8 <= N <= 10000). Далее,
> даны координаты коня и короля. Поставить конем шах
> королю за наименьшее число ходов (король не двигается).
> Сначала показалась довольно несложной. Hо как сел
> решать - ... Кроме перебора (хоть и неполного), на
> ум ничего не приходит. Интуиция, правда, подсказывает,
> что здесь алгоритм Дейкстры может быть полезен, но
> с какого боку - загадка... :) Может, кто уже сталкивался
> с такой задачкой, знает способ решения?
Волна действительно может помочь. Просто надо обрабатывать не соседние
клетки, а расположенные буквой Г. Hо для доски 10000*10000 это ИМХО будет
слишком долго.
Так что либо пускать волну в узком коридоре, либо приблизиться конем по
кратчайшей траектории (либо каждым ходом минимизируя max(DeltaX, DeltaY),
либо минимизируя расстояние от коня до прямой, соединяющей начальную и
конечную точки - а-ля алгоритм Брезенхейма) к некоторой окрестности (порядка
8-10 клеток) короля, а уже оттуда пускать волну. Правда есть вероятность,
что последний вариант не даст наилучшего решения.
С уважением, Андрей.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Интересная задача 
