ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexei Emanov                        2:5059/4.48    01 Jul 2001  12:34:53
 To : Aleksey Mashihin
 Subject : Re: help
 -------------------------------------------------------------------------------- 
 

 
 01 июля 2001 года (а было тогда 00:44)
 Aleksey Mashihin в своем письме к All писал:
 [skip]
 
  AM> Я использовал алгаритм Дейкстры, но он как-то не правильно работает
  AM>   Т.е. если есть схема типа 1--2--3--4 и перекрыть 3 кран, то он все
  AM> равно пишет что в 4 вода есть !
 
 По-моему, тебе должен подойти алгоритм Ли (aka "волновой"):
 Короче, дело было так:
 У тебя есть массив(выходной), в котором будут помечены те вершины, в которых
 вода есть. Hазовем это массив A.  У тебя есть очередь со списком вершин, из
 которых течет вода.  Изначально очередь содержит вершину, из которой вода
 начинает распространяться. Hа каждом шаге, ты обрабатываешь первую вершину в
 очереди. Обработка выглядит примерно так:
 1) Извлечь элемент из очереди, это будет вершина v
 2) Ищешь все вершины, в которые вода может попасть, и добавляешь их в конец  
 очереди.
 3) Если очередь содержит элементы, вернемся на шаг 1, иначе выходим из цикла  
 обработки.
 
 Вот собственно. Просто и со вкусом. По крайней мере, мне этот вкус нравится. Ж)
 [skip]
 
 С уважением, Alexei                           01 июля 2001 года
 
 http://amigo.seo.nsc.ru/HTMLChanger/ - Программа для поиска и замены текста
 http://members.download.ru/cgi-bin/download.cgi?2162&rus
 
 --- GoldED+/W32 1.1.4.7
  * Origin:  (2:5059/4.48)
 
 

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

Тема:    Автор:    Дата:    help   Aleksey Mashihin   01 Jul 2001 00:44:41   Re: help   Alexei Emanov   01 Jul 2001 12:34:53   help   Aleksey Golubin   01 Jul 2001 23:58:37   Re: help   Pavel Fomin   02 Jul 2001 20:25:34