As per request, here's how you need to go about to create a non-recursive solution:
There are probably many different approaches, but the easiest to explain in this context, is simply turning the recursion upside-down:
The recursion works by calculating the results for the smaller sized problem, and deriving the solution for the full-sized problem from that. The iterative solution reverts this approach, by solving the smallest size problems, and iteratively derive the solutions for the next larger sized problems. Obviously, you need to store the intermediate results somehow, and you need to make sure that you get all the smaller solutions that you need in the next step.
For this problem, the partial problems to solve iteratively are the maximum value and number of maximum paths from one of the end points to one position in the NxN matrix. To keep track of these two values, I'd suggest creating a simple struct. And to keep track of all partial solutions, I'd create a NxN array of these structs:
struct sum_paths {
int sum;
int num_paths;
};
struct path_results {
int rows;
int columns;
sum_paths* results;
int at (int row, int column)
{
return row*columns+column;
}
void set_at(int row, int column, int sum, int npaths)
{
results[at(row, column)].sum = sum;
results[at(row, column)].num_paths = npaths;
}
sum_paths get_at(int row, int column)
{
return results[at(row, column)];
}
};I've added a few utility functions to simplify reading and writing.
You'll start in one corner - in the spirit of your recursive program that roots its recursion in the lower right corner, I'd suggest starting in the lower right corner. The maximum value to reach that position is 0, because there is no value assigned to this cell, and the number of paths is 1, so you assign (0,1) to the result array at position (N-1,N-1) :
path_results results;
int row = N-1;
int column = N-1;
results.set_at(row, column, 0, 1);
Next you can derive the correct values for the bottom row, going right to left. You need to be careful that you should only set a value != 0 here if there is actually a path leading to the cell to your right, and the current cell is not blocked:
for (column = N-2; column >= 0; --column)
{
int sum = 0;
int npaths = 0;
if (A[row][column] != 'x')
{
npaths = results.get_at(row, column+1).num_paths;
if (npaths > 0)
sum = A[row][column]-'0' + results.get_at(row, column+1).sum;
}
results.set_at(row, column, sum, npaths);
}
Next you continue from bottom to top and right to left, to fill in the results set. You have to be careful when checking and combining the results from the cells to your right, from below, and from the lower right: first you need to find out which path yields the maximum sum, and then you need to add the paths from each direction that does yield this result. And of course you always need to check whether there is a valid path in either direction to start with.
Eventually your process will reach cell [0][0], and you can print out the result.
I'll leave the details of the implementation as an exercise for you. If you don't get the result 4, I suggest that you use the debugger on the last example to find out what is going wrong. (and yes, the fact that I know the result means I do have a working program - but you really should try this on your own)
P.S.:
Here's the code I used to print out not only the final result, but also the entire array of intermediate results. I've found it rather helpful to locate some subtle bugs I've introduced in early versions of my code. You might find it helpful, too:
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j)
cout << results.get_at(i, j).sum << ' ';
cout << endl;
}
cout << endl;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j)
cout << results.get_at(i, j).num_paths << ' ';
cout << endl;
}
cout << endl;
cout << "maximum sum: " << results.get_at(0,0).sum << endl;
cout << "number of paths: " << results.get_at(0,0).num_paths << endl;
Submit an article or tip