|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 25 Nov 2001 03:59:32
To : Vitaly Slobodskoy
Subject : Re: RE:Интересная задача
--------------------------------------------------------------------------------
"Vitaly Slobodskoy" <Vitaly.Slobodskoy@p22.f128.n5015.z2.fidonet.org> wrote
in message news:1006637195@p22.f128.n5015.z2.ftn...
> AD> Дана шахматная доска NxN (8 <= N <= 10000). Далее,
> AD> даны координаты коня и короля. Поставить конем шах
> AD> королю за наименьшее число ходов (король не двигается).
> AD> Сначала показалась довольно несложной. Hо как сел
> AD> решать - ... Кроме перебора (хоть и неполного), на
> AD> ум ничего не приходит. Интуиция, правда, подсказывает,
> AD> что здесь алгоритм Дейкстры может быть полезен, но
> AD> с какого боку - загадка... :) Может, кто уже сталкивался
> AD> с такой задачкой, знает способ решения?
> Попробуй нарисовать волну для некоторых n ходов. Я уверен, там есть
> закономерность. Если ее выведешь, то сможешь вычислять путь, зная
положение
> короля.
1) Как я понял, проблем с краем поля вроде бы нет, система
кооодинат может быть выбрана произвольно, и можно считать,
что конь начинает с поля 0,0
2) Задача имеет симметрию и можно рассматривать ее
как будно король находится в i,j и j<=i.
3) Гипотеза: для приближения к королю надо сделать
N ходов (+1,+2); M ходов (+2,+1) и, возможно, один-два любых
других.
4) Задача упрощантся еще и тем, что мы точно знаем, четное
или нечетное количество ходов потребуется.
5) Строим вокруг короля поле ходов конем, на 1-2 хода,
добавляем саму позицию короля и пытаемся для каждого
поля из этой окрестности найти комбинацию
i =N+2*M,
j=2*N+M.
Откуда, соответственно,
N =(2j-i)/3,
M=(2i-j)/3.
Если для поля i,j значения N и М - целые, то сохраняем это поле
и даем ему вес N+M+(расстояние до короля).
6) Из всех сохраненных полей выбираем поле с наименьшим
весом. Дорога до этого поля - в соответствии с (3) в любом
порядке, и уже в окрестности короля - по матрице ходов конем.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: RE:Интересная задача 