//	DANI HOROWITZ
//	NOVEMBER 2004
 
/***************************************************************************/
/***************************************************************************/
 
//		CSC 155 Project 2 Dynamic Programming 
//			Assigned 11/02/2004
//			  Due : 11/16/2004
//
//
 
#include <iostream.h>
int	*Rectangular_Shortest_Path(int , int , int , int , int[][6], int[][6]);
 
int	*Rectangular_Shortest_Path(int startx, int starty, int endx, int endy, 
				   int r[][6], int a[][6])
{
	// I could find no easy way to dynamically create a 2D array in C++
	int distance[10][10];			// keep track of distances to get to each point
	int path[10][10];				// keep track of the best paths
 
	/***************************************************************************/
	/***************************************************************************/
 
	int size = (endx-startx)+(endy-starty);		// size of our shortest path array
	int* shortest_path = new int[size];			// it will take 8 steps to get from (0,0)->(5,5)
	cout << "It will take " << size << " steps" << endl;
 
	/***************************************************************************/
	/***************************************************************************/
 
	// populate our starting place
	distance[startx][starty] = 0;
 
	// populate bottom distance row
	for (int x=startx+1; x<=endx; x++)
	{
		distance[x][starty] = distance[x-1][starty] + r[x-1][starty];
		cout << "We went right to get to (" << x << "," << starty << ") in " << distance[x][starty] << " units" << endl;
	}
 
	// populate leftmost distance row
	for (int y=starty+1; y<=endy; y++)
	{
		distance[startx][y] = distance[startx][y-1] + a[startx][y-1];
		cout << "We went up to get to (" << startx << "," << y << ") in " << distance[startx][y] << " units" << endl;
	}
 
	/***************************************************************************/
	/***************************************************************************/
 
	cout << endl;
	for (int y=starty+1; y<=endy; y++)	// go down each column
	{
		for (int x=startx+1; x<=endx; x++)	// go across each row
		{
			int distance_up = distance[x][y-1] + a[x][y-1];			// calculate weight to get to (x,y) from coordinate below it
			int distance_right = distance[x-1][y] + r[x-1][y];		// calculate weight to get to (x,y) from coordinate to left of it
			if (distance_up < distance_right)	// it's better to move up
			{
				distance[x][y] = distance_up;		// populate our distance array
				path[x][y] = 1;						// populate our path array
				cout << "If we go up to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
			}
			else								// it's better to move right
			{
				distance[x][y] = distance_right;	// populate our distance array
				path[x][y] = 0;						// populate our path array
				cout << "If we go right to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
			}
		}
	}
 
	/***************************************************************************/
	/***************************************************************************/
 
	x = endx;
	y = endy;
	int n=0;
	cout << endl << "Working backwards ..." << endl;
	// now that we have all of the smaller problems solved to calculate the optimal weight to get to every point on the grid,
	// let's figure out how to get from (5,5)->(1,1)
 
	while (x >= startx && y >= starty)	// loop so long as both coordinates are >= 1
	{
		if (x > startx && y > starty)
		{
			// we are not working in the first row or first column,
			// which means that we have an opportunity of going left or down, whichever is best
 
			if ((distance[x-1][y]+r[x-1][y]) < (distance[x][y-1]+a[x][y-1]))
			{
				cout << "Go left from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
				x--;	// move one unit left
			}
			else
			{
				cout << "Go down from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
				y--;	// move one unit down
			}
		}
		else
		{
			if (x == startx)	// we are somewhere in the left column
			{
				// we don't have a choice, we can only move down
				cout << "Go down from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
				y--;
			}
			else				// we are somewhere in the bottom row
			{
				// we don't have a choice, we can only move left
				cout << "Go left from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
				x--;
			}
		}
		shortest_path[n] = path[x][y];		// populate our shortest path array - this line has an error ??
		n++;
	}
 
	cout << endl;
 
	/***************************************************************************/
	/***************************************************************************/
 
	return shortest_path;	// return the shortest path BACKWARDS!
 
}
 
 
int	main()
{
 
	int	Right[6][6]; 	// entry Right[i][j] contains the link distance  
				// between grid point (i,j) to (i+1, j);
	int	Above[6][6]; 	// entry Above[i][j] contains the link distance  
				// between grid point (i,j) to (i, j+1);
 
	int	*shortest_path; // the array for storing the shortest path 
 
	//
	// read the inputs for the 2-dimensional arrays Right and Above 
	//
 
	for (int i=1; i< 6; i++)
	{
		for (int j=1; j < 6; j++)
		{
	cout << "Please enter the link distance : Right[" << i << "," << j << "]\n";
			cin  >> Right[i][j];
	cout << "Please enter the link distance : Above[" << i << "," << j << "]\n";
			cin  >> Above[i][j];
		}
 
	}
	shortest_path = Rectangular_Shortest_Path(1,1,5,5, Right, Above);
 
	return (0);
}