# Author: Ryan Bridges - 9/30/2017

# Given a cost matrix cost[][] and a position (m, n) in cost[][], write a
# function that returns cost of minimum cost path to reach (m, n) from (0, 0).
# Each cell of the matrix represents a cost to traverse through that cell.
# Total cost of a path to reach (m, n) is sum of all the costs on that path
# (including both source and destination). You can only traverse down, right and
# diagonally lower cells from a given cell, i.e., from a given cell (i, j),
# cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. You may assume
# that all costs are positive integers.


def min_cost_path(graph, n, m):
    dp_matrix = [[0 for x in range(0,len(graph[0]))] for y in range(0, len(graph))]

    # Initialize top left corner
    dp_matrix[0][0] = graph[0][0]

    # Initialize top row
    for i in range(1, len(graph[0])):
        dp_matrix[0][i] = dp_matrix[0][i - 1] + graph[0][i]

    # Initialize left column
    for i in range(1, len(graph)):
        dp_matrix[i][0] = dp_matrix[i - 1][0] + graph[i][0]

    # Fill in the rest
    for i in range(1, len(graph)):
        for j in range(1, len(graph[0])):
            dp_matrix[i][j] = graph[i][j] + min(dp_matrix[i][j - 1], dp_matrix[i - 1][j], dp_matrix[i - 1][j - 1])
            if (j, i) == (n, m):
                return dp_matrix[i][j]

    # Return -1 if the point specified is not on the graph
    return -1

graph = [[0 for x in range(0, 4)] for y in range(0, 3)]
graph[0][0] = 1
graph[0][1] = 2
graph[0][2] = 3
graph[0][3] = 3
graph[1][0] = 4
graph[1][1] = 8
graph[1][2] = 2
graph[1][3] = 3
graph[2][0] = 1
graph[2][1] = 5
graph[2][2] = 3
graph[2][3] = 3

print min_cost_path(graph, 3, 2)
