Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Flood fill solution in Clear category for Calculate Islands by nickie
from collections import deque
neighbors = [(-1, -1), (0, -1), (+1, -1),
(-1, 0), (+1, 0),
(-1, +1), (0, +1), (+1, +1)]
def checkio(data):
n, m = len(data), len(data[0])
aces = set((i, j) for i in range(n) for j in range(m) if data[i][j] == 1)
islands = []
while aces:
c = aces.pop()
area = 1
q = deque([c])
while q:
(i, j) = q.popleft()
for (di, dj) in neighbors:
n = (i+di, j+dj)
if n in aces:
aces.remove(n)
area += 1
q.append(n)
islands.append(area)
islands.sort()
return islands
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0]]) == [1, 3], "1st example"
assert checkio([[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 1, 0, 0]]) == [5], "2nd example"
assert checkio([[0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0]]) == [2, 3, 3, 4], "3rd example"
Oct. 14, 2013
Comments:
