Центр фигуры

From

Andrey Dashkovsky (2:5002/46.4)

To

Alexander Kolosov

Date

2002-11-25T22:51:10Z

Area

RU.ALGORITHMS

Hello Alexander.

23 Ноя 02 20:34, you wrote to Andrew Starsh:

 AK>>> Нужно определить координаты центра фигуры обозначенной
 AK>>> единицами. Насколько я понял, нужно достроить фигуру до
 AK>>> прямоугольника и найти пересечение его диагоналей. Какой
 AK>>> алгоритм лучше использовать?

 AS>> Имхо, куда как пpоще сделать так: найти сpеднюю стpоку, (n-1)/2+1,
 AS>> где n - количество непустых стpок. Потом опpеделить во всех
 AS>> непустых стpоках самую левую непустую колонку (L) и самую пpавую
 AS>> непустую (R). (R-L)/2+1 Все это конечно, если фигуpы коppектны -
 AS>> то есть, непустых стpок - нечетно, и непустых колонок - тоже.

 AK> Да. Забыл сказать, что таких фигур в матрице может быть несколько,
 AK> например так:

 AK> 0000000
 AK> 0110011
 AK> 0110001
 AK> 0111001
 AK> 0000000
 AK> 0011110
 AK> 0000110

 AK> И для каждой нужно найти центр.

Я вот подумал, можно же воспользоваться обычной заливкой. Про заливку как-то
обсуждалось, скажу только обязательно делать не рекурсией, а эмуляцией рекурсии
и при этом использовать не стек, где начинать с последней запомненной клетки, а
очередь, т.е. продолжать с той клетки, которая была запомненна первой, и при
этом заливать не одну клетку, а строку сразу из найденной клетки, а можно даже:
              5
            442444
        44443323335
       53333331344444
        43333323333335
         444332333344
         5333323334
          44445444
Типа 1 - это точка с которой начинается заливка, 2 - это определяем границы по
вертикали, 3 - это заливаем всё, что можем, 4 - это те вершины, что ложим в
очередь, а 5 - это границы фигуры. А в процессе заливки несложно запоминать мин
и макс по обеим осям.

Andrey

... - У Вас совесть есть? - Есть, только мы ее не используем.
--- GoldED+/386 1.1.4.7
 * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)