GCJ2009 - Qualification - B - Watershed

# Statement

The statement for this problem can be found in the Google CodeJam 2009 page, or click this link

# Solution

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 source code (GCJ2009-Q-B.py):

```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()
```