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 PositronicLlama
"""Determine the size of the largest connected group of numbers in a matrix."""
import itertools
def flood(number, matr, x, y, open, unexplored):
"""
Push x, y into open if it hasn't already been explored and contains number.
"""
n = len(matr)
if 0 <= x < n and 0 <= y < n:
if matr[x][y] == number:
if (x, y) in unexplored:
open.add((x, y))
unexplored.remove((x, y))
def checkio(matr):
'''
Given matrix NxN (3<=N<=10).
Numbers between 1 and 5 are elements of A.
Find the biggest union of the same numbers in group and the number.
Say, group is a bunch of numbers that stay near each other.
'''
# Solve using O(N*N) flood fill
n = len(matr)
unexplored = set(itertools.product(range(n), repeat=2))
best = 0
best_count = 0
while unexplored:
x, y = unexplored.pop()
number = matr[x][y]
count = 0
open = set([(x, y)])
while open:
x, y = open.pop()
count += 1
# Attempt to flood fill in each dirction
flood(number, matr, x + 1, y, open, unexplored)
flood(number, matr, x - 1, y, open, unexplored)
flood(number, matr, x, y + 1, open, unexplored)
flood(number, matr, x, y - 1, open, unexplored)
if count > best_count:
best = number
best_count = count
return [best_count, best]
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], 'First'
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], 'Second'
print('All ok')
Dec. 7, 2012
Comments:
