I have a n*n
matrix, where each element represents an integer. Starting in [0,0]
I have to find the path of exactly m
elements down to the last row, returning the maximum cost. The path can end in any column on the last row and n ≤ m ≤ n^2
I thought of finding all paths of length m
from [0,0]
to [n-1, 0], [n-1, 1] ... [n-1, n-1]
. But it does not feel optimal...
Which algorithm would be the most efficient way of doing this? BFS or DFS?
EDIT
Possible directions are down/right/left, but only visit each element at most once.
EDIT 2
So for example, if this matrix is given (n=4):
[ 1 4 1 20 ]
[ 5 0 2 8 ]
[ 6 8 3 8 ]
[ 3 2 9 5 ]
And m=7, the path could be
[ → → → ↓ ]
[ 5 0 2 ↓ ]
[ 6 8 3 ↓ ]
[ 3 2 9 x ] = Path cost = 47
or
[ ↓ 4 1 20 ]
[ ↓ 0 2 8 ]
[ → → ↓ 8 ]
[ 3 2 → x ] = Path cost = 32
or if m = n^2
[ → → → ↓ ]
[ ↓ ← ← ← ]
[ → → → ↓ ]
[ x ← ← ← ]
EDIT 3 / SOLUTION
Thanks to Wanderley Guimar?es,
http://ideone.com/0iLS2