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