ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Serge Kanilo                         2:5020/400     29 Oct 2001  03:55:39
 To : Andrew Akapiev
 Subject : Re: конь
 -------------------------------------------------------------------------------- 
 

 "Andrew Akapiev" <Andrew.Akapiev@p119.f160.n5015.z2.fidonet.org> wrote in
 message news:1004297288@p119.f160.n5015.z2.FIDOnet.ftn...
 
 > Провести белого коня из клетки с заданными координатами x1,y1 в клетку с
 > координатами x2,y2 за минимальное число ходов, но при условии, что на
 
 шахматной
 
 > доске расположено N белых пешек (координаты известны).
 > Ясно, что конь не может ходить на место с пешкой. Мой вариант - перебрать
 
 все
 
 > восемь возможных ходов, а когда конь на краю доски, то их меньше, и если
 
 это
 
 > место не занято пешкой, то посмотреть, не увеличивается ли расстояние до
 
 точки
 
 > назначения и выбрать тот ход, при котором расстояние минимально.
 > Да, еще есть подозрения, что нужно учитывать клетки, на которых конь уже
 
 был,
 
 > чтобы избежать зацикливания.
 
 Помечаем клетки с пешками как занятые, остальные точки - как незанятые.
 Ставим 0 - в точку цели, длина_пути_до_цели=0 и делаем следующее:
   для всех точек содержащих длину_пути_до_цели делаем все возможные
   ходы конем в незанятые точки и присваиваем им значение
 длина_пути_до_цели+1,
   и отмечаем их как занятые.
 Продолжаем это до тех пор, пока не дойдем до исходной точки положения коня.
 Hу а теперь обратный путь. Из начальной точки ходом коня выбираем первую
 попавшуюся с номером на 1 меньше чем в текушей, и делаем ее текушей, пока
 не дойдем до конечной точки со значением 0.
 Hу и на обратном пути выводим пройденные точки на печать.
 
 Cheers,
 Serge
 
 --- ifmail v.2.15dev5
  * Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор