Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import copy
- import sys
- def greater_path(path1,path2):
- (path_list1,elevation1,last_heightl1) = path1
- (path_list2,elevation2,last_heightl2) = path2
- len1 = len(path_list1)
- len2 = len(path_list2)
- if len1 != len2:
- return len1 > len2
- return elevation1 > elevation2
- def get_neighbours(arrsize,point):
- rcount,ccount = arrsize
- i,j = point
- deltas = [(-1,0),(0,-1),(1,0),(0,1)]
- points = ((x+i,y+j) for (x,y) in deltas)
- points = filter(lambda (x,y): (x>=0 and x<rcount) and (y >= 0 and y<ccount),points)
- return points
- def is_higher(arr,point1,point2):
- i,j = point1
- ii,jj = point2
- return arr[i][j] < arr[ii][jj]
- def split_neighbours(neighbours,arr,i,j):
- higher,lower = [],[]
- higher = filter(lambda (x,y): is_higher(arr,(i,j),(x,y)),neighbours)
- lower = filter(lambda (x,y): not is_higher(arr,(i,j),(x,y)),neighbours)
- return higher,lower
- def get_max(path1,path2):
- return path1 if greater_path(path1,path2) else path2
- def update_paths(paths,arr,i,j):
- elevation = arr[i][j]
- arrsize = len(arr),len(arr[0])
- neighbours = get_neighbours(arrsize,(i,j))
- higher_neighbours,lower_neighbours = split_neighbours(neighbours,arr,i,j)
- lower_paths = [paths[neighbour] for neighbour in lower_neighbours if paths.get(neighbour) is not None]
- if lower_paths == []:
- paths[(i,j)]=([(i,j)],0,elevation)
- else:
- path,elevation_sofar,last_elevation = reduce(get_max,lower_paths)
- path = copy.deepcopy(path)
- path.append((i,j))
- paths[(i,j)] = (path,elevation_sofar+elevation-last_elevation,elevation)
- for ii,jj in higher_neighbours:
- update_paths(paths,arr,ii,jj)
- def solve(arr,paths):
- for i,row in enumerate(arr):
- for j,point in enumerate(row):
- update_paths(paths,arr,i,j)
- def get_array_from_file(f):
- a = []
- row,col = map(int,f.readline().split())
- i = 0 ;
- while i < row:
- a.append(map(int,f.readline().split()))
- i=i+1
- return a
- if __name__ == '__main__':
- paths = {}
- f = None
- if len(sys.argv) == 1:
- f = sys.stdin
- else:
- f = open(sys.argv[1],"r")
- arr = get_array_from_file(f)
- solve(arr,paths)
- print reduce(get_max,paths.values())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement