uf2.py

import string

class UnionFind(object):
    def __init__(self, size):
        # not enough
        self.weights = range(size)

    def union(self, a, b):
        # Add top-left rule
        smaller_letter, bigger_letter = sorted((
            self.weights[a], self.weights[b]
        ))

        # Make all bigger == smaller
        for idx in xrange(len(self.weights)):
            if self.weights[idx] == bigger_letter:
                self.weights[idx] = smaller_letter


def get_neighbours(matrix, idx, width, height):
    y = idx / width
    x = idx % width

    res = []
    order_of_importance = iter(xrange(0, 4))

    if y - 1 >= 0:
        key = (y-1) * width + x
        res.append(
            (matrix[key], next(order_of_importance), key)
        )

    if x - 1 >= 0:
        key = y * width + (x - 1)
        res.append(
            (matrix[key], next(order_of_importance), key)
        )

    if x + 1 < width:
        key = y * width + (x + 1)
        res.append(
            (matrix[key], next(order_of_importance), key)
        )

    if y + 1 < height:
        key = (y+1) * width + x
        res.append(
            (matrix[key], next(order_of_importance), key)
        )
    
        # Better use a heap
    return sorted(res)[0]


def main():
    with open('watershed.txt') as f:
        n_cases = int(f.readline())

        for _ in xrange(n_cases):
            # Pluck width and height
            height, width = map(int, f.readline().split(' '))

            # Create union find datastructure
            uf = UnionFind(width * height)

            matrix = []
            for _ in xrange(height):
                matrix.extend(map(int, f.readline().split(' ')))

            for idx, el in enumerate(matrix):
                cost, _, neighbour_id = get_neighbours(matrix, idx, width, height)
                if cost < el:
                    uf.union(idx, neighbour_id)

            letters = iter(string.ascii_lowercase)
            d = {}
            iter_weights = iter(uf.weights)
            for _ in xrange(height):
                cs = []
                for _ in xrange(width):
                    num = next(iter_weights)
                    try:
                        cs.append(d[num])
                    except KeyError:
                        char = d[num] = next(letters)
                        cs.append(char)
                print ' '.join(cs)


if __name__ == '__main__':
    main()