Шлюхи без блекджека, блекджек без шлюх. Войти !bnw Сегодня Клубы
Есть битмап из черных и белых точек. Надо оставить на нем только связанные области, состоящие из менее чем k точек. Пока придумал алгоритм за два прохода чуть более чем по O(n²) каждый (первый проход нумерует точки в каждой связной области слева направо сверху вниз, второй соответственно удаляет в обратном порядке), можно ли быстрее? Интерес чисто теоретический, j4f.
Рекомендовали: @l29ah @o01eg
#RHCTL4 / @lexszero / 4817 дней назад

Посмотри, как сделано в Conway's Game of Life, ты же что-то такое хочешь.
#RHCTL4/G3X / @siranthony / 4817 дней назад
помоему нет ничего оптимальней, чем найти все свяазанные области и выбрать из них подходящие, а это можно сделать и за один проход - бежим по всем точкам, если точка с кем-то смежна - бежим туда и находим всю область, запомнив, что в тех точках уже были. Заодно сохраняем найденную область если ее длина меньше К. кажется, ничего быстрее нет, но как это доказать - хз.
#RHCTL4/RMC / @virginal / 4817 дней назад
@siranthony не вижу никакой связи с game of life, и вообще там каждая итерация - ровно количество клеток на поле.
#RHCTL4/Z7S / @lexszero --> #RHCTL4/G3X / 4817 дней назад
@lexszero Значит я не понял, что ты хочешь, ну ладно.
#RHCTL4/SUP / @siranthony --> #RHCTL4/Z7S / 4817 дней назад
ipv6 ready BnW для ведрофона BnW на Реформале Викивач Котятки

Цоперайт © 2010-2016 @stiletto.