Ваш алгоритм имеет недостатки.Рассмотрим следующий пример:
11110
01010
10010
11101
Ваш алгоритм содержит 2 компонента, тогда как он имеет только 1.
Для тестирования я использовал эту слегка измененную версию вашего кода.
import sys
def CompCount(image):
l = len(image[0])
b = len(image)
prev = curr = [sys.maxint]*(l+1)
nextComp = 0
tree = dict()
for i in xrange(b):
curr = [sys.maxint]*(l+1)
for j in xrange(l):
curr[j] = sys.maxint
if image[i][j] == '0':
p = [prev[j+n] for m,n in [(1,1),(-1,0),(-1,-1)] if 0<=i+m<b and 0<=j+n<l and image[i+m][j+n] == '0']
curr[j] = min([curr[j]] + p + [curr[j-1]])
if curr[j] == sys.maxint:
nextComp += 1
curr[j] = nextComp
tree[curr[j]] = 0
else:
if curr[j] < prev[j+1]: tree[prev[j+1]] = curr[j]
if curr[j] < prev[j]: tree[prev[j]] = curr[j]
if curr[j] < prev[j-1]: tree[prev[j-1]] = curr[j]
if curr[j] < curr[j-1]: tree[curr[j-1]] = curr[j]
prev = curr
return len([x for x in tree if tree[x]==0])
print CompCount(['11110', '01010', '10010', '11101'])
Позвольте мне попытаться объяснить ваш алгоритм словами (с точки зрения графика, а не сетки).
- Установить «корни» как пустое множество.
- Итерировать поузлы на графике.
- Для узла n посмотрите на все его соседи, уже обработанные.Назовите этот набор A.
- Если A пусто, выберите новое значение k, установите v [узел] равным k, и добавьте k к корням.
- В противном случае, пусть k будет минимальнымv [узел] для узла в A. Удалите v [x] из корней для каждого x в A с v [x]! = k.
- Число компонентов - это числоэлементов корней.
(Ваш tree совпадает с моим roots: обратите внимание, что вы никогда не используете значение tree[] элементов, только если они равны 0 или нет ..это просто реализация набора)
Это похоже на union-find, за исключением того, что предполагается, что при объединении двух компонентов тот, который имеет более высокое значение v [], никогда ранее не объединялся с другим компонентом.В контрпримере это используется, потому что два 0 в центральном столбце были объединены с 0 слева.