/**
**  If we could move to any direction in the path, then we kind of use 
**  Dijkstra's algorithm to solve this problem. The difference with the
**  shotest path problem in graph is that in the graph, different node 
**  to one node may have path with different weight. But int the grid,
**  each neighbor to this cell would sum with the same value. So if we
**  would also get minimun sum in fisrt calculate for this cell.
**
**
**  Since the question ask to move either right or down only, then the
**  question merely become Robort move question. With dynamic programming
**  we could solve it in O(mn) time complexity.
**/


#include <iostream>
#include <vector>
#include <map>

using namespace std;

//Left or down only
int MinPathSum2(vector<vector<int> > &grid) 
{
    if (grid.size() <=0) return 0;

    size_t row = grid.size()-1;
    size_t col = grid[0].size()-1;

    for (int i = row; i > 0; --i)
        grid[i-1][col] += grid[i][col];

    for (int j = col; j > 0; --j)
        grid[row][j-1] += grid[row][j];

    for (int i = row-1; i >= 0; --i)
        for (int j = col-1; j >=0; --j)
            //sum with the less one
            grid[i][j] += 
                grid[i+1][j] < grid[i][j+1]? 
                        grid[i+1][j] : grid[i][j+1];

    return grid[0][0];
}

//Dijkstra's algorithm
int MinPathSum(vector<vector<int> > &grid) 
{
    if (grid.size() <=0) return 0;

    size_t row = grid.size();
    size_t col = grid[0].size();

    if(row == 1 && col == 1)return grid[0][0];

    //indicate whether the path in grid has been visited
    vector<vector<bool> > visited(row, vector<bool>(col,false));

    --row, --col;//max index in row and column

    typedef pair<size_t,size_t> PathIndex;
    //the contains contains all calculated pathes,
    //key: current sum from source to this path, 
    //pair: index in the grid
    multimap<int, PathIndex > pathes;

    pathes.insert(pair<int, PathIndex>(grid[0][0],PathIndex(0,0)));
    visited[0][0] = true;


    while(!pathes.empty())
    {
        //get next path with minmun sum value
        multimap<int, PathIndex >::iterator it = pathes.begin();
        int value = (*it).first;
        int i = (*it).second.first;
        int j = (*it).second.second;
        pathes.erase(it);

        //if the cell is just next to the right-bottom most cell
        //we find the result, just return the sum
        if (i == row-1 && j == col)
            return value + grid[row][col];
        if (i == row && j == col-1)
            return value + grid[row][col];

        //calculate sum of each cells neart current choosen one

        //up neighbor
        if (i > 0 && !visited[i-1][j])
        {
            pathes.insert(
                pair<int, PathIndex>(value + grid[i-1][j],
                    PathIndex(i-1, j)));
			
			grid[i-1][j] += value;
            visited[i-1][j] = true;
        }
        //bottom neighbor
        if (i < row && !visited[i+1][j])
        {
            pathes.insert(
                pair<int, PathIndex>(value + grid[i+1][j],
                    PathIndex(i+1, j)));
            visited[i+1][j] = true;
        }

        //left neighbor
        if (j > 0 && !visited[i][j-1])
        {
            pathes.insert(
                pair<int, PathIndex>(value + grid[i][j-1],
                    PathIndex(i, j-1)));
            visited[i][j-1] = true;
        }

        //right neighbor
        if (j < col && !visited[i][j+1])
        {
            pathes.insert(
                pair<int, PathIndex>(value + grid[i][j+1],
                    PathIndex(i, j+1)));
            visited[i][j+1] = true;
        }
    }

    return 0; //the function will never reach this line
}

void InitVV(vector<vector<int> >& v, int * array)
{
	if(v.size() <=0) return;
	
	int col = v[0].size();
	for (int i = 0 ; i<v.size(); ++i)
	{
		for (int j = 0; j < col; ++j)
		{
			v[i][j] = array[col*i + j];
			//cout << v[i][j] << ',';
		}
		
		//cout << '\n';
			
	}
	
	//cout << endl;
}

int main(int argc, char** argv)
{
    //[[1,3,1],[1,5,1],[4,2,1]] 
    vector<vector<int> > grid1(3, vector<int>(3));
    grid1[0][0] = 1;
    grid1[0][1] = 3;
    grid1[0][2] = 1;
    grid1[1][0] = 1;
    grid1[1][1] = 5;
    grid1[1][2] = 1;
    grid1[2][0] = 4;
    grid1[2][1] = 2;
    grid1[2][2] = 1;
    cout << MinPathSum2(grid1) << endl;

    vector<vector<int> > grid2(1, vector<int>(1));
    grid2[0][0] = 3;
    cout << MinPathSum2(grid2) << endl;
	
    int a3[][11] = {  
        {1,0,4,9,6,0,9,1,8,9,5},
        {1,2,8,9,2,4,8,1,7,3,2},
        {5,0,7,9,3,5,1,3,8,2,3},
        {3,2,2,5,3,3,3,2,0,5,6},
        {9,6,8,3,6,2,0,1,4,6,1},
        {1,7,4,8,8,9,7,1,3,2,5},
        {7,7,8,0,3,0,0,0,8,1,8},
        {8,7,4,0,9,5,4,7,9,8,5},
        {5,6,3,5,5,6,0,7,1,7,7},
        {9,9,2,1,1,2,1,5,0,0,4}
	};
	
	vector<vector<int> > grid3(10, vector<int>(11));
	InitVV(grid3,a3[0]);
    cout << MinPathSum2(grid3) << endl;
	
	
	
    return 0;
}