ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexey Varlamov                      2:5005/67      24 Aug 2001  00:33:00
 To : Dmitry Ukstin
 Subject : Алгоpитм кольца
 -------------------------------------------------------------------------------- 
 

 *** Ответ на сообщение из RU.ALGORITHMS (Algorithms - search and discussions). 
 Привет Dmitry!
 
 21 Aug 01 20:23, Dmitry Ukstin -> All:
 
  DU> Суть задачи:
  DU> Имеется матpица скажем 9х9 заполненная пpоизвольно числами 0 и 1.
  DU> Hаходясь в опpеделенной позиции (пpедположим Y=3, X=4) опpеделить не 
  DU> обpазуют ли значения матpицы, pавные 1, замкнутую область (кольцо).
 
   Я бы эту задачу решал с помощью алгоритма заливки:
 
   Чтобы перекрасить фигуру одного цвета в другой, вызываем функцию
 перекраски точки X,Y, лежащей внутри фигуры. Эта функция проверяет:
   ЕСЛИ точка еще не перекрашена (т.е. исходного цвета), то:
  1. Перекрашиваем точку в новый цвет
  2. Вызываем функцию перекраски для точки X-1,Y     (рекурсивный вызов)
  3. Вызываем функцию перекраски для точки X+1,Y
  4. Вызываем функцию перекраски для точки X,Y-1
  5. Вызываем функцию перекраски для точки X,Y+1
   ИHАЧЕ рекурсивный вызов не производим (т.е. возврат на предыдущий уровень 
 рекурсии).
 
  Теперь о задаче: Идея в том, чтобы залить пространство вне фигуры каким-то 
 цветом. Если внутри фигуры есть "островки", то они не перекрасятся и их 
 можно обнаружить. Для того, чтобы гарантированно иметь сплошное 
 пространство _вне_ фигуры, в программе используем матрицу, немного большую,
 чем в условии - пусть по периметру будет ободок из нулей. (Для случая, если 
 фигура у самого края или даже занимает все поле).
 
 Итак, задачу решаем за три этапа:
 1. Перекрашиваем фигуру в особый (отличный от других) цвет - пусть это
   будет цвет "-1". Hачальная точка перекраски нам дана.
 2. Перекрашиваем пространство вне фигуры (для этого можно начать с левого 
 верхнего угла) в третий цвет (например, 2). При этом цвета 0 и 1 считаем 
 за один цвет, поэтому перекрасится и свободное пространство, и посторонние 
 фигуры и "островки" в посторонних фигурах. 
   Точки особого цвета (-1) не перекрашиваем. Они станут преградой для 
 перекраски "островков" внутри фигуры.
 3. Теперь пробегаемся по полю и ищем неперекрашенные точки (с цветом 0).
 Если таких точек нету (все либо -1, либо 2), то фигура незамкнута.
    Если есть точки 0-го цвета, то фигура замкнута и эти точки лежат внутри 
 фигуры (внутри фигуры так же могут лежать и посторонние фигуры с цветом  1).
 
 Все. Программу, я думаю, напишешь сам. 
 
 Alexey
 
 --- Fregate 1.52/W32
  * Origin: Solwo Station, ph.411019 (22:00-08:00) (2:5005/67)
 
 

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

Тема:    Автор:    Дата:    Алгоpитм кольца   Alexey Varlamov   24 Aug 2001 00:33:00   Алгоpитм кольца   Alexey Varlamov   24 Aug 2001 01:10:00