In [11]:

    

def solve(grid, no_rows, no_columns):
    w, h = no_columns, no_rows;
    result_mat = [[5000000 for x in range(w)] for y in range(h)]
    
    result_mat[0] = grid[0]
    
    for row in range (0, no_rows-1):
        for col in range(0, no_columns):
            result_mat[row+1][col] = min(result_mat[row+1][col], grid[row+1][col] + result_mat[row][col])
            if col+1 < no_columns:
                result_mat[row+1][col+1] = min(result_mat[row+1][col+1], grid[row+1][col+1] + result_mat[row][col])
            
            if col-1 >= 0:
                result_mat[row+1][col-1] = min(result_mat[row+1][col-1], grid[row+1][col-1] + result_mat[row][col])
    
    result = 5000000
    for i in range(0, no_columns):
        result = min(result, result_mat[no_rows-1][i])
        
    print result


    

In [12]:

    

props = map(int, raw_input().split())

no_rows = props[0]
no_columns = props[1]

grid = [[None for x in range(no_columns)] for y in range(no_rows)] 

for i in range(0, no_rows):
    bus = map(int, raw_input().split())
    for j in range(0, no_columns):
        grid[i][j] = bus[j]
    
solve(grid, no_rows, no_columns)


    

    




5 5
1 3 1 2 6
10 2  5  4  15
10 9  6  7  1
2  7  1  5  3
8  2  6  1  9
[[1, 3, 1, 2, 6], [11, 3, 6, 5, 17], [13, 12, 9, 12, 6], [14, 16, 10, 11, 9], [22, 12, 16, 10, 18]]
10

In [ ]: