ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Anton Tikhonov                       2:5020/400     28 May 2003  11:21:49
 To : Artur Mogozov
 Subject : Задача
 -------------------------------------------------------------------------------- 
 

  AM> Hа шахматной доске размером N x N стоит конь, который ходит по обычным
  AM> шахматным правилам. Hадо найти самый короткий путь из исходной клетки в
  AM> заданную. Hекоторые поля считаются запрещенными, на них фигуру ставить
  AM> нельзя.
  AM> Если путь не существует вообще, вывести сообщение об этом.
 
 Я бы сделал так - 
 каждой клетке поля присваивается число ф(к) - за сколько ходов из 
 этой клетки можно попасть в целевую клетку. В целевой ставится 0, 
 во всех остальных сначала - maxint - очень большое число
 целевая клетка заносится в стек
 
 Пока в стеке что-нибудь есть
   достать из стека клетку А
   для каждой из 8 клеток Б, в которые можно пойти конем из А
   (кроме запрещенных Б)  
     если ф(А)+1 < ф(Б) то
       ф(Б):=ф(А)+1
       Б записать в стек
     конец
   конец
 конец
 
 если после этого на начальной позиции коня стоит maxint -> 
 путь не существует
 если число - оно и есть мин расстояние до искомой клетки
 
 Скорей всего, есть и более быстрые алгоритмы, и скорей всего при 
 размере доски 500 в 1 секунду этот не уложится...
 
 Антон
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    Задача   Artur Mogozov   28 May 2003 11:45:07   Задача   Anton Tikhonov   28 May 2003 11:21:49   Задача   Sam   28 May 2003 14:23:22   Re: Задача   Andrew Ezhguroff   28 May 2003 14:24:54   Задача   Serge Nozhenko   28 May 2003 15:36:36   Задача   Mity Usanov   28 May 2003 23:05:03   Задача   Igor Bychkov   29 May 2003 00:29:11