|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Slobodskoy 2:5015/128.22 25 Nov 2001 01:26:35
To : Alexey Desyatnik
Subject : RE:Интересная задача
--------------------------------------------------------------------------------
AD> Тут мне приспичило для олимпиады по программированию
AD> задачку придумать. Вот что на ум пришло:
AD>
AD> Дана шахматная доска NxN (8 <= N <= 10000). Далее,
AD> даны координаты коня и короля. Поставить конем шах
AD> королю за наименьшее число ходов (король не двигается).
AD>
AD> Сначала показалась довольно несложной. Hо как сел
AD> решать - ... Кроме перебора (хоть и неполного), на
AD> ум ничего не приходит. Интуиция, правда, подсказывает,
AD> что здесь алгоритм Дейкстры может быть полезен, но
AD> с какого боку - загадка... :) Может, кто уже сталкивался
AD> с такой задачкой, знает способ решения?
Попробуй нарисовать волну для некоторых n ходов. Я уверен, там есть
закономерность. Если ее выведешь, то сможешь вычислять путь, зная положение
короля.
ПОКА!
--- F.I.P.S./32 v1.0r W95/NT [M]
* Origin: Жить вредно - от этого умирают! (2:5015/128.22)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
