|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Astafiev 2:5000/228.16 24 Nov 2001 15:52:06
To : Alexey Desyatnik
Subject : Интересная задача
--------------------------------------------------------------------------------
AD> Тут мне приспичило для олимпиады по программированию
AD> задачку придумать. Вот что на ум пришло:
AD>
AD> Дана шахматная доска NxN (8 <= N <= 10000). Далее,
AD> даны координаты коня и короля. Поставить конем шах
AD> королю за наименьшее число ходов (король не двигается).
AD>
AD> Сначала показалась довольно несложной. Hо как сел
AD> решать - ... Кроме перебора (хоть и неполного), на
AD> ум ничего не приходит. Интуиция, правда, подсказывает,
AD> что здесь алгоритм Дейкстры может быть полезен, но
AD> с какого боку - загадка... :) Может, кто уже сталкивался
AD> с такой задачкой, знает способ решения?
AD>
AD> Заранее благодарен за любую информацию
вероятно, наименьшее количество ходов будет в линии соединяющую коня и короля.
Двигаться нужно аппроксимируя линию ходом коня буквой Г. Вероятно,
проведя первую линию от коня до короля, вторую - от еороля до коня и посмотрев
где они пересекаются (соединив их) получим оптимальный путь?
--- Alex Raider / Flash inc.
* Origin: Alex Raider/ Flash inc. 1992-2001 (2:5000/228.16)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
