#include <iostream>
#include <algorithm>
#include "grid.h"    // Or use boost::multi_array
using namespace std;

double MinPathCost(Grid<double>& costs)
{
	/* Keep track of answers to subproblems. */
	Grid<double> minCosts(costs.numRows(), costs.numCols());
	
	/* Cost of path from 0, 0 to itself is the cost of the grid at (0, 0) */
	minCosts(0, 0) = costs(0, 0);

	/* If in the first column, only legal move is to go up.  Compute the
	 * cost of a solution from here as the cost of the current location plus
	 * the cost of moving downward.
	 */
	for (size_t i = 1; i < costs.numRows(); ++i)
		minCosts(i, 0) = minCosts(i - 1, 0) + costs(i, 0);

	/* Similarly, in the first row you can only move left. */
	for (size_t j = 1; j < costs.numCols(); ++j)
		minCosts(0, j) = minCosts(0, j - 1) + costs(0, j);
	
	/* For any other location, take the better of moving up and moving left.
	 * The cost is that cost plus the cost of the current location.
	 */
	for (size_t i = 1; i < costs.numRows(); ++i)
		for (size_t j = 1; j < costs.numCols(); ++j)
			minCosts(i, j) = min(minCosts(i - 1, j), minCosts(i, j - 1)) + costs(i,j);

	/* Our answer is in the bottom-right corner. */
	return minCosts(minCosts.numRows() - 1, minCosts.numCols() - 1);
}