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()
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License