А) присвоить значение начальной точки текущей и пометить ее
А) присвоить значение начальной точки текущей и пометить ее;
б) в восьми направлениях просмотреть — нет ли рядом стоящих фишек (не далее
одной клетки, и не помеченных ранее) если найдена точка, то (в), иначе (г);
в) перейти в найденную точку и пометить ее (г);
г) если текущая точка не начальная, то перейти в ранее занимаемую точку (б),
иначе (д)
д) поиск закончен.
Для наглядности алгоритм представлен на рисунке (?)
Алгоритм поиска в глубину позволяет последовательно обойти все вершины графа (в
нашем случае все рядом стоящие точки одного цвета). Чтобы находить точки,
образующие замкнутое кольцо, необходимо дополнить поиск следующим условием:
Если в результате поиска мы вернулись в начальную вершину и путь из этой
вершины не совпадает с тем путем по которому вернулись в нее, то найден цикл
(см. рис. 3)
Алгоритм поиска в глубину
Рис. 2
6) шестое правило предполагает заполнение полученного замкнутого контура
точками захватившего. Чтобы это реализовать необходимо найти точку, которая
находится внутри контура и используя алгоритм поиска в глубину закрасить
помеченные точки одним цветом при следующих условиях:
а) поиск ведется в четырех направлениях (чтобы не «выскочить» из контура между
поставленными углом фишками) (см. рис. 4);
Оставить комментарий