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