Minimum Cost – Land Acquisition: The government of India plans to build a road In a city. The government also plans to acquire some lands to start the construction. The program must accept an Integer matrix of size N*N representing the heights of the buildings (i.e., the number of storeys In each building) in the city. A positive value X in the matrix indicates that there is an X-storey building. A zero value in the matrix indicates the presence of land that cannot be acquired by the government.
The rules for road construction In the city are given below.
– The road always starts from the first row and ends at the last row.
– No more than one building In a row can be acquired by the government.
The cost to acquire an X-storey building is X. The government has decided to acquire the lands with the minimum cost M. The program must print the minimum cost M to acquire land for road construction in the given city as the output.
NOTE: It is always possible to build a road In the given city.
The first line contains N.
The next N lines, each contains N Integers separated by space.
The first line contains M.
Example Input/Output 1:
0 0 2 0
1 3 4 5
5 0 7 0
8 1 2 3
Example Input/Output 2:
1 2 0
4 3 1
5 2 1
n=int(input()) mat=[list(map(int,input().split())) for r in range(n)] for r in range(1,n): for c in range(0,n): if mat[r][c]==0: continue building= if c!=0 and mat[r-1][c-1]!=0: building.append(mat[r-1][c-1]) if c!=n-1 and mat[r-1][c+1]!=0: building.append(mat[r-1][c+1]) if mat[r-1][c]!=0: building.append(mat[r-1][c]) if building: mat[r][c]+=min(building) else: mat[r][c]=0 print(min([i for i in mat[n-1] if i!=0]))