Flood filling contiguous areas on a 2D grid

floodfill.py

#!/usr/bin/python

import random
import sys

# Given an XxY array...
X = 24
Y = 16

# ... This is modelled as nested lists for O(1) element access times
# where the data type is an integer.  0 is the base state, -1 is a node
# that hasn't been processed yet, and > 0 is one that and has been colored.
# To improve the algorithm later on we will surround the grid with a
# perimeter of sentinels.
GRID = []
for _ in range(0, Y+2):
    GRID.append((X+2) * [0])

def print_grid():
    for row in GRID[1:-1]:
        print ''.join('{:3d}'.format(x) for x in row[1:-1])

# Next lets add some 'random' data to the grid, we'll use M * N / 2 which
# will yield approximately 50% nodes in the unprocessed state
random.seed(0)
for _ in range(0, X*Y >> 1):
    x = random.randint(1, X)
    y = random.randint(1, Y)
    GRID[y][x] = -1


# The main problem, given the grid, how many blocks exist which consist of
# contiguous nodes in a the vertical and horizonal planes.  We iterate over
# the grid taking into account the sentinels...
COLOR = 0
for y in range(1, Y+1):
    for x in range(1, X+1):
        # Ignore anything we haven't visited
        if GRID[y][x] != -1:
            continue
        # The fun bit, based on Dijkstra/A* depth first searches we are going
        # to color contiguous blocks via a filling algorithm, like the paint bucket
        # in MS Paint...
        COLOR += 1
        queue = [(x, y)]
        seen = set()
        while queue:
            # Pop the closest node to the source and colour it in
            node = queue.pop(0)
            GRID[node[1]][node[0]] = COLOR
            # Next move N,S,E,W pushing valid coordinates onto the queue
            for move in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                tx = node[0] + move[0]
                ty = node[1] + move[1]
                if GRID[ty][tx] != -1:
                    continue
                coord = (tx, ty)
                queue.append(coord)
                seen.add(coord)

# The answer to our problem is the last color seen.
print 'Solution: {} blocks'.format(COLOR)

# And dump out the grid for sanity checking
print_grid()

# vi: ts=4 et: