﻿Minimum Cost - Land Acquisition
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.
Input Format: 
The first line contains N. 
The next N lines, each contains N Integers separated by space. 

Output Format: 
The first line contains M.

Example Input/Output 1: 
Input: 
4 
0 0 2 0 
1 3 4 5
5 0 7 0
8 1 2 3
Output: 
11

Example Input/Output 2: 
Input: 
3
1 2 0
4 3 1
5 2 1
Output: 
4
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]))
