|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nikolaj Kovaltchuk 2:463/552.432 27 Nov 2001 08:17:34
To : Alex Astafiev
Subject : Интересная задача
--------------------------------------------------------------------------------
AD>> Дана шахматная доска NxN (8 <= N <= 10000). Далее,
AD>> даны координаты коня и короля. Поставить конем шах
AD>> королю за наименьшее число ходов (король не двигается).
AD>> Сначала показалась довольно несложной. Hо как сел
AD>> решать - ... Кроме перебора (хоть и неполного), на
AD>> ум ничего не приходит. Интуиция, правда, подсказывает,
AD>> что здесь алгоритм Дейкстры может быть полезен, но
AD>> с какого боку - загадка... :) Может, кто уже сталкивался
AD>> с такой задачкой, знает способ решения?
AA> вероятно, наименьшее количество ходов будет в линии соединяющую коня и
AA> короля. Двигаться нужно аппроксимируя линию ходом коня буквой Г.
AA> Вероятно, проведя первую линию от коня до короля, вторую - от еороля
AA> до коня и посмотрев где они пересекаются (соединив их) получим
AA> оптимальный путь?
А если конь изначально стоит на соседней с коpолем клетке?
*_/С почтением, HиколайКа./_*
--- [NikolajKa, Ravlik. EMail: nikolajka@svitonline.com]
* Origin: Еще не придумал (2:463/552.432)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
