//
// Checkerboard traversal
// Assignment 5 for CSC 321
//
// John D. Rogers
//

#include <iostream>
#include <fstream>
#include <stack>

using namespace std;

void printMaximumProfitRoute(int n, int** r, int rstar);

void computeMaximumProfit(int n, int **p, int **w, int **r, int& profit, int& rstar);

//
// Read the description of the checkerboard profit maximization problem
// in the web page write-up for assignment 5 and in the textbook on p. 368.
//
// Briefly, the input consists of an n-by-n table p where p[i][j] contains
// the profit for square i, j.  Your function should compute the entries of
// the table w, where w[i][j] is the maximal winnings a checker can earn by
// starting in row 1 and going to square i, j.  The table r is used to keep 
// track of the route the checker took in getting to square i, j.  So r[i][j]
// contains the column of the square in row i-1 that the checker visited 
// before landing on square i, j.
//
// The parameters profit and rstar are call-by-reference.  The first one, profit,
// contains the maximum profit that can be earned by starting the checker on 
// the first row and moving it to row n.  The second one, rstar, is the column
// in row n where the checker ends up.
//

//
// The program assumes the data is coming from a text file with the name
// "cbtdata.txt" and with the format:
//
// n
// p1,1 p1,2, ..., p1,n
// p2,1 p2,2, ..., p2,n
// ...
// pn,1 pn,2, ..., pn,n
//
int main()
{
	int n;
	ifstream inputfile;
	inputfile.open("cbtdata.txt");
	inputfile >> n;

	int **p;  // n-by-n table of profits
	int **w;  // n-by-n table of winnings
	int **r;  // n-by-n table of route information
	int rstar, profit;
	
	p = new int*[n+1];
	w = new int*[n+1];
	r = new int*[n+1];

	for (int i = 1; i <= n; i++) {
		p[i] = new int[n+1];
		w[i] = new int[n+1];
		r[i] = new int[n+1];
	}


	for (i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			inputfile >> p[i][j];
		}
	}

	computeMaximumProfit(n, p, w, r, profit, rstar);

	cout << "Maximum Profit is " << profit << endl;

	printMaximumProfitRoute(n, r, rstar);

	return 0;
}