Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Flood fill solution in Clear category for Radiation Search by nickie
from collections import deque
neighbors = [(0, -1), (-1, 0), (+1, 0), (0, +1)]
def checkio(data):
n, m = len(data), len(data[0])
left = set((i, j) for i in range(n) for j in range(m))
biggest = [0, None]
while left:
(i, j) = left.pop()
size = 1
mark = data[i][j]
q = deque([(i, j)])
while q:
(i, j) = q.popleft()
for (di, dj) in neighbors:
n = (i+di, j+dj)
if n in left and data[i+di][j+dj] == mark:
left.remove(n)
size += 1
q.append(n)
if size > biggest[0]:
biggest = [size, mark]
return biggest
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([
[1, 2, 3, 4, 5],
[1, 1, 1, 2, 3],
[1, 1, 1, 2, 2],
[1, 2, 2, 2, 1],
[1, 1, 1, 1, 1]
]) == [14, 1], "14 of 1"
assert checkio([
[2, 1, 2, 2, 2, 4],
[2, 5, 2, 2, 2, 2],
[2, 5, 4, 2, 2, 2],
[2, 5, 2, 2, 4, 2],
[2, 4, 2, 2, 2, 2],
[2, 2, 4, 4, 2, 2]
]) == [19, 2], '19 of 2'
Dec. 15, 2013
