説明からは、問題の正確な制約が何であるかは明確ではありません。左、右、上、下のゼロでクラスターを区別できると仮定すると、次の問題が解決します...
#!/usr/bin/env python
data = [ #top-left
[0,0,1,1,0,0],
[0,0,1,1,0,0],
[1,1,0,0,1,1],
[1,1,0,0,1,1],
[0,0,1,1,0,0],
[0,0,1,1,0,0],
[1,1,0,0,1,1],
[1,1,0,0,1,1],
] # bottom-right
d = {} # point --> clid
dcl = {} # clid --> [point1,point2,...]
def process_point(t):
global clid # cluster id
val = data[t[0]][t[1]]
above = (t[0]-1, t[1])
abovevalid = 0 <= above[0] < maxX and 0 <= above[1] < maxY
#below = (t[0]+1, t[1]) # We do not need that because we scan from top-left to bottom-right
left = (t[0], t[1]-1)
leftvalid = 0 <= left[0] < maxX and 0 <= left[1] < maxY
#right = (t[0], t[1]+1) # We do not need that because we scan from top-left to bottom-right
if not val: # for zero return
return
if left in d and above in d and d[above] != d[left]:
# left and above on different clusters, merge them
prevclid = d[left]
dcl[d[above]].extend(dcl[prevclid]) # update dcl
for l in dcl[d[left]]:
d[l] = d[above] # update d
del dcl[prevclid]
dcl[d[above]].append(t)
d[t] = d[above]
elif above in d and abovevalid:
dcl[d[above]].append(t)
d[t] = d[above]
elif left in d and leftvalid:
dcl[d[left]].append(t)
d[t] = d[left]
else: # First saw this one
dcl[clid] = [t]
d[t] = clid
clid += 1
def print_output():
for k in dcl: # Print output
print k, dcl[k]
def main():
global clid
global maxX
global maxY
maxX = len(data)
maxY = len(data[0])
clid = 0
for i in xrange(maxX):
for j in xrange(maxY):
process_point((i,j))
print_output()
if __name__ == "__main__":
main()
それは印刷します...
0 [(0, 2), (0, 3), (1, 2), (1, 3)]
1 [(2, 0), (2, 1), (3, 0), (3, 1)]
2 [(2, 4), (2, 5), (3, 4), (3, 5)]
3 [(4, 2), (4, 3), (5, 2), (5, 3)]
4 [(6, 0), (6, 1), (7, 0), (7, 1)]
5 [(6, 4), (6, 5), (7, 4), (7, 5)]