0

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 1th 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 1th 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:

  1. 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

  2. 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(mn). Is there any optimal solution or dynamic-programming algorithms fit this problem?

Thanks, sorry for long question

Community
  • 1
  • 1

1 Answers1

1

How there can be both 0-th and m-th rows in a matrix with total m rows?

Anyway, a simple Dijkstra will give you an optimal path in O(n*m) (assuming you have a good data structure to find minimum in the list of not yet reached points).

Also, if your knight can move only down the board (it can be useful to move up sometimes to decrease total path weight), you can write simple DP. Just start from the bottom of the board and for each position calculate how much it'll take to reach bottom. Since you can do up to 4 moves from each position, it's a simple check for minimum. Something like this

for (int row = m - 1; row >= 0; --row) {
    for (int col = 0; col < m; ++col) {
        int path1 = a[row][col + 1] + a[row][col + 2] + a[row + 1][col + 2] + best[row + 1][col + 2];
        int path2 = a[row][col + 1] + a[row + 1][col + 1] + a[row + 2][col + 1] + best[row + 2][col + 1];
        int path3 = ...
        int path4 = ...
        best[row][col] = min(path1, path2, path3, path4);
    }
}

edit
Why do you need to go up? Imagine matrix like this (where * means some ridiculously big number, like 1000000000). Obviously, you'll have to go from (0, 0) to the right part of the board before you go down.

111111111111
111111111111
*********111
*********111

So, path will look like this

...1...1...1
11...1...1..
*********11.
*********11.
Nikita Rybak
  • 67,365
  • 22
  • 157
  • 181
  • of course I mean 1 - m'th or 0th - (m-1)'th . I'm now editing –  Dec 23 '10 at 13:58
  • 1
    You can go up but why do you need to do this? because the all numbers are all positive –  Dec 23 '10 at 14:03
  • If numbers are all positive you can find a solution, otherwise the problem could not have a solution. Imagine for example to have 2 moves starting from A and returning to A (i.e. a loop) with a negative sum. The best solution would be exploiting that loop infinitely to decrease the path weight to -INF... – digEmAll Dec 23 '10 at 14:20
  • 1
    you don't necessarily have to move from 0,0. The question says from first row (in any column) to the last row (in any column), then your example is not correct. Anyway, you could need to go up though. I would draw an example but it's impossible in a comment...(this last sentence smells like Fermat...) – digEmAll Dec 23 '10 at 14:29
  • @digEmAll Yeah, I missed 'first row' part. Anyway, as you noted, it's pretty easy to correct this example. – Nikita Rybak Dec 23 '10 at 14:32