Hi,

I have an intriguing problem that looks like a travelling salesman problem but I want to see whether someone has a better solution. So what I have is an NxM matrix with both positive and negative numbers (ints):

NxM
  |      b             a
--+-------------------------
  | 1    4    5   -1   9   ...
  | 0    3    0   17  -3   ...
b>| 1   10    3    0   3   ...
  |-8   -3    2    1  -4   ...
a>| 0    8    4    0   0
...
[download]

My starting position is (a,a) = 0
My end position is  (b,b) = 10
[download]

What Iam looking for is a path that has the highest total sum from aa > bb

pathA: left, up, left, left, up =  0+0+1+2+(-3)+10 = 10
pathB: left-slide + up-slide = 0+8+10 = 18   
pathC: up-slide + left + up + left-slide+down = 0+3+0+17+3+10= 33

etc..
[download]

From the above it follows that I can slide or I can go by one position in any direction except the diagonal. Given a starting position (x - any random position) the task is to discover the value in the matrix (let say N=10, M=10) so that the number of moves (summing operations) from x to that position is the minimum possible and the total sum (summarized values) of the path is the maximum possible. In tha above example path C would be the best candidate but i haven't worked out all possible paths so I don't know. Is there a clever (meaning fast) way to compute this?

thank you