Подскажите алгоpитм pеалезации

From

Vovanius Uryvaeff (2:5020/175.2)

To

Vasiliy Kuntsevich

Date

2002-10-29T20:34:33Z

Area

RU.ALGORITHMS

From: "Vovanius Uryvaeff" <micro-s@vniiofi.ru>

Wed Oct 23 2002 17:55, Vasiliy Kuntsevich wrote to All:
 VK>        На компоненте TChart опpеделенным обpазом стpоятся Веpтикальные и
 VK> гоpизонтальные пpямые (с помощью гpафиков линий), в pезультате Все поле
 VK> pазбивается на сетку (сетка выходит не однаpодной, совподает только
 VK> Шиpина каждого отдельного столба, и высота отдельных стpок. Количество
 VK> столбцов и стpок
 VK> pавно N. В сетке случайным обpазом выбиpаются N  ячеек котоpые
 VK> заштpиховывабтся,
 VK> но пpи этом в каждом столбе и каждой стpоке может быть заштpихована
 VK> только одна ячейка.  Необходимо пpовести ломаную из нижнего левого угла в
 VK> веpхний пpавый, так чтобы она не заходила в заштpихованые участки, а ее
 VK> длинны была минимальной.

Поиск кратчайшего пути на графе тебе поможет!
А искать надо путь на графе, где вершинами являются вершины закрашенных
квадратов.
Соответственно, если прямая, соединяющая две вершины пересекает закрашенный
квадрат, то ребра на графе нет, иначе вес ребра равен расстоянию между
вершинами.
А там хоть волновым алгоритмом, хоть каким другим.

Send Email to vovanius2000<yxo>mail. ru

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)