Find Maximum sum in a path in a 2D matrix with positive integers

Question

I would like to know where I can read about algorithms for solving this problem efficiently:

• Four directions allowed: up, down, left, right
• Cells containing zero can't be visited.
• Visiting the same cell twice is illegal.
• Moves wraps around the edges:
• (first row is connected with last row)
• (first col is connected with last col)

Example, 5x5 and 5 steps:

  9  1  3  1  9
  6  3  2  4  1
  0  7  *  7  7
  5  4  9  4  9
  7  9  1  5  5

Starting point: *

Solution: down,left,down,left,down. That is 9 + 4 + 9 + 7 + 9 = 38

 [9] 1  3  1  9
  6  3  2  4  1
  0  7  *  7  7
  5 [4][9] 4  9
 [7][9] 1  5  5

This problem is probably not related to:

• Finding the maximum sub matrix
• Dynamic programming

Answer 1

You specified in comments that you wanted a sub-second way of finding the best value 20-step path out of a 5x5 matrix. I've implemented a basic recursive search tree that does this. Ultimately, the difficulty of this is still O(3^k), but highly saturated cases like yours (21 out of 24 allowed nodes visited) will solve much faster because the problem simplifies to "skip the n*n-z-k-1 lowest value cells" (in this case, n=5, z=1 and k+1 = 21; the winning path skips three 1's).

The problem instance in your question solves in 0.231seconds on a 3 year old i5 laptop and about half a second on ideone.com. I've provided code here http://ideone.com/5kOyxq (note that 'up' and 'down' are reversed because of the way I input the data).

For less saturated problems you may need to add a Bound/Cut method. You can generate a Bound as follows:

First, run over the NxN matrix and collect the K highest value elements (can be done in N² log K) and sort them by max-first. Then, cumulatively calculate the value UB[t] = SUM[i::0->t] SortedElements[i]. So, any t-length path has a UB of UB[t] (max t elements).

At step T, the current Branch's UB is UB[t]. If ValueSoFar[T] + UB[K-T] <= BestPathValue, you can stop that branch.

There may be better ways, but this should be sufficient for reasonably sized matrices and path lengths.

Answer 2

Game or puzzle. Given a matrix, number of steps and a sum, find the path. Would be nice if there is a real world application for this, but i haven't found it. Games tend to "burn in" knowledge in young brains, so why not burn in something useful, like addition?

Answer 3

#include<iostream>
#include<climits>
#define R 3
#define C 3

int MAX(int x, int y, int z);

int Max_Cost(int cost[R][C], int m, int n)
{
   if (n < 0 || m < 0)
      return INT_MIN;

   else if (m == 0 && n == 0)
      return cost[m][n];

   else
      return cost[m][n] + MIN( Max_Cost(cost, m-1, n-1),
                               Max_Cost(cost, m-1, n), 
                               Max_Cost(cost, m, n-1)
                             );
}

int MAX(int x, int y, int z)
{
  return max(max(x, y), z);
}

int main()
{
  int cost[R][C] = { {3, 2, 5},
                     {5, 8, 2},
                     {9, 7, 1}
                   };
  cout<<Max_Cost(cost, 2, 1);

  return 0;
}