StarCraft FOREVER - Показать сообщение отдельно - Тема для волосатых мужиков (задача с графом)
Показать сообщение отдельно
Старый 19.07.2011, 11:22   #1
uti
Местный
 
Аватар для uti
 
Регистрация: 16.06.2004
Сообщений: 3,753
Нарушения: 14
ICQ:
Тема для волосатых мужиков (задача с графом)

Пишу свою браузерную игру с маджонгом и гейшами. Возникла следующая проблема.

Есть поле из гексов и некий источник энергии, от которого она может распространяться по всем ячейкам. При этом поток может разделяться и объединяться сколь угодно раз. Но в нём не должно быть циклов. Проще говоря, если двигаться по любым энергетическим веткам вдоль "течения", то никогда нельзя оказаться в одной ячейке более одного раза, то есть нельзя сделать петлю.
Как детектить такое замыкание?
Зелёный - как можно. Красный - как нельзя.

p.s. На одном форуме порекомендовали топологическую сортировку, но я что-то не понял, как её тут применить.


Последний раз редактировалось uti; 19.07.2011 в 11:30.
uti вне форума   Ответить с цитированием