In the amusement park at Jooney’s amusement, there is a “Weighted Maze” challenge. This consist of a set of East West roads and North South roads (referred to as up down roads). There are N intersections and each intersection has a block of iron bar, the weight of which is given. You enter the maze at the top left corner. The exit from the maze is at the bottom right corner. Movement at any intersection is to the right or down provided a road exists in that direction.
At each Intersection you pass through, you must exchange the weight in your cart with the weight of the bar at the intersection if it is heavier than the weight in you have in the cart.
The objective is to determine a path through the maze along the roads so that one can exit the maze with the minimum weight in the cart.
Boundary Condition(s):
2 <= N <= 100
Input Format:
The first line contains the number of intersections N.
Output Format:
The first line contains the minimum weight in the cart at the exit.
Example Input/Output 1:
Input:
4
1,8,21,7
19,17,10,20
2,18,23,22
14,25,4,13
Output:
22
n=int(input())
MAT=[list(map(int, input().split(','))) for i in range(n)]
way=[[0]*n for i in range(n)]
way[0][0]=MAT[0][0]
for i in range(1,n):
way[0][i]=max(way[0][i-1], MAT[0][i])
way[i][0]=max(way[i-1][0], MAT[i][0])
for r in range(1,n):
for c in range(1,n):
value=min(way[r-1][c],way[r][c-1])
way[r][c]=max(value, MAT[r][c])
print(way[-1][-1])