Рекурсивный алгоритм или алгоритм заливки растра?

У меня есть такой двоичный растр:

101101
010111
101011
111101

Теперь мне нужно сделать это построчно: пройти по строке и подсчитать соседние ячейки, которые равны 1 (только ячейки в строке!). И я хотел бы получить вектор или что-то в этом роде. например, для растра выше это будет:

1st row: 1 2 1

2nd row: 1 3

3rd row: 1 1 2

4th row: 4 1

Я много читал об алгоритме заливки флудом и так далее. Но я просто не понимаю.

Я попробовал этот рекурсивный алгоритм:

rec=function(x)
   {if (x==0)
       {return 0)
    else return(1+rec(x+1))}

Но это не работает.


r recursion algorithm flood-fill
person Cocilein    schedule 16.12.2016    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Вы можете попробовать использовать rle.

xy <- read.table(text = "1 0 1 1 0 1
0 1 0 1 1 1
1 0 1 0 1 1
1 1 1 1 0 1", sep = "")
xy

apply(xy, MARGIN = 1, FUN = function(x) {
  x <- rle(x)
  x$lengths[x$values == 1]
})

[[1]]
V2 V5    
 1  2  1 

[[2]]
V3    
 1  3 

[[3]]
V2 V4    
 1  1  2 

[[4]]
V5    
 4  1
person Roman Luštrik    schedule 16.12.2016

arrow_upward
0
arrow_downward

Вам вообще не нужен алгоритм заполнения заливки. Рекурсия тоже не нужна.

Просто посчитайте не нули. Простейший конечный автомат:

Starting state in the beginning of every line is 0
When state is 0 and you meet 1, remember X-position Start and make state 1
When state is 1 and you meet 0, make state 0 and add `Current - Start` to list
In other cases do nothing
person MBo    schedule 16.12.2016
comment
ок большое спасибо за ваш ответ! Я попробовал это, и это сработало для небольшого растра. Но мне приходится иметь дело с большими растрами (180х480) и это занимает слишком много времени. Возможно, моя версия просто недостаточно эффективна. - person Cocilein; 16.12.2016
comment
У этого алгоритма наилучшее время выполнения — он посещает каждый растровый элемент только один раз. Он должен быть молниеносным для любого разумного размера растра. - person MBo; 16.12.2016