minimum L sum in a mxn matrix - 2
- by hilal
Here is my first question about maximum L sum and here is different and hard version of it.
Problem : Given a mxn *positive* integer matrix find the minimum L sum from 0th row to the m'th row . L(4 item) likes chess horse move
Example : M = 3x3
0 1 2
1 3 2
4 2 1
Possible L moves are : (0 1 2 2), (0 1 3 2) (0 1 4 2)
We should go from 0th row to the 3th row with minimum sum
I solved this with dynamic-programming and here is my algorithm :
1. Take a mxn another Minimum L Moves Sum array and copy the first row of main matrix. I call it (MLMS)
2. start from first cell and look the up L moves and calculate it
3. insert it in MLMS if it is less than exists value
4. Do step 2. until m'th row
5. Choose the minimum sum in the m'th row
Let me explain on my example step by step:
M[ 0 ][ 0 ] sum(L1 = (0, 1, 2, 2)) = 5 ; sum(L2 = (0,1,3,2)) = 6; so MLMS[ 0 ][ 1 ] = 6
sum(L3 = (0, 1, 3, 2)) = 6 ; sum(L4 = (0,1,4,2)) = 7; so MLMS[ 2 ][ 1 ] = 6
M[ 0 ][ 1 ] sum(L5 = (1, 0, 1, 4)) = 6; sum(L6 = (1,3,2,4)) = 10; so MLMS[ 2 ][ 2 ] = 6
...
the last MSLS is :
0 1 2
4 3 6
6 6 6 Which means 6 is the minimum L sum that can be reach from 0 to the m.
I think it is O(8*(m-1)*n) = O(m*n). Is there any optimal solution or dynamic-programming algorithms fit this problem?
Thanks, sorry for long question
