CodeJam 2009 - Qualification Round - (B)Watersheds - Solution

Today, I'm posting the solution for problem B in 2009's Qualification Round which was called "Watersheds".

You can find the statement of the problem in the Google CodeJam page or follow this link.

The solution is straightforward, without any tricks.
For each cell in the map I throw a recursive function which checks whether that cell is already in a basin or it calls recursively with the cell where the water goes to.
In case that the water can't go any further then a new basin is set at that cell and returned so that  the rest of the recursive calls set theirs to that basin.

The python file is GCJ2009-Q-B.py and it contains the following:

last_letter = 'a'
W = 0
H = 0

def run_water(height_map, basin_map, i, j):
    global last_letter, H, W
    if basin_map[i][j]:
        return basin_map[i][j]
    min_h = height_map[i][j]
    direction = 0
    if i > 0 and height_map[i-1][j] < min_h:
        direction = 1
        min_h = height_map[i-1][j]
    if j > 0 and height_map[i][j-1] < min_h:
        direction = 2
        min_h = height_map[i][j-1]
    if j < W-1 and height_map[i][j+1] < min_h:
        direction = 3
        min_h = height_map[i][j+1]
    if i < H-1 and height_map[i+1][j] < min_h:
        direction = 4
        min_h = height_map[i+1][j]
    if direction == 0:
        basin_map[i][j] = last_letter
        last_letter = chr(ord(last_letter) + 1)
    elif direction == 1:
        basin_map[i][j] = run_water(height_map, basin_map, i-1, j)
    elif direction == 2:
        basin_map[i][j] = run_water(height_map, basin_map, i, j-1)
    elif direction == 3:
        basin_map[i][j] = run_water(height_map, basin_map, i, j+1)
    elif direction == 4:
        basin_map[i][j] = run_water(height_map, basin_map, i+1, j)
    return basin_map[i][j]

def solve():
    global last_letter, H, W
    H, W = map(int, input().split(' '))
    height_map = []
    for i in range(H):
        height_map.append(list(map(int, input().split(' '))))
    basin_map = [[''] * W for i in range(H)]
    last_letter = 'a'
    for i in range(H):
        for j in range(W):
            run_water(height_map, basin_map, i, j)
    for i in range(H):
        print(' '.join(basin_map[i]))

if __name__ == '__main__':
    T = int(input())
    for case in range(1, T+1):
        print("Case #{0}:".format(case))
        solve()