another mouse and cheese problem... in a 2d field :P

[gregorynoob]

given x and y (the field dimensions) and x*y numbers, (pieces of cheese on each square) calculate the best way for the mouse to get from (1, 1) to (x, y), he has to get as many cheese as possible... also you can only move closer to the (x, y) (so he couldn't eat the whole field).
i tried going through a row while it's sum is higher than the column's and switching them that way but i kinda failed... is there an efficient algorithm to solve this problem? ...i'd just like a clue

[ArkM]

It's C++ programming forum. Where is C++ in your post?..

[VernonDozier]

It's C++ programming forum. Where is C++ in your post?..

There's no "Algorithm" or "Game Theory" section in Daniweb (as far as I know), so if gregorynoob is doing this in C++ and needs algorithm/strategy help, it seems like the right forum.

given x and y (the field dimensions) and x*y numbers, (pieces of cheese on each square) calculate the best way for the mouse to get from (1, 1) to (x, y), he has to get as many cheese as possible... also you can only move closer to the (x, y) (so he couldn't eat the whole field).
i tried going through a row while it's sum is higher than the column's and switching them that way but i kinda failed... is there an efficient algorithm to solve this problem? ...i'd just like a clue

I'd say you need three two-dimensional arrays. cheese[a][b] represents the amount of cheese at square (a, b). totalcheese[a][b] represents the amount of cheese eaten on the optimal path from (a,b) to (x,y). direction[a][b] is the direction to take (up or right) from (a,b) if you are on the optimal path to (x,y). Optimal path will be the path where you eat the most cheese.

If a == x , there is no calculation to be made. You must go up since going right takes you farther away from (x, y). Ditto when b == y . You must go right for the same reason.

When a < x and b < y you need to compare totalcheese[a+1][b] to totalcheese[a][b+1] . Pick the greater and go that direction. In the event of a tie, pick either one. That means that totalcheese[a+1][b] and totalcheese[a][b+1] must be known before calculating totalcheese[a][b] , so you'll be starting at (x,y) and moving away from it.

If you are moving up from (a,b), totalcheese[a][b] = totalcheese[a][b+1] + cheese[a][b] .

That should be enough to get you started, I hope.

[Salem]

> i'd just like a clue
Draw a grid on some paper, and experiment with various strategies.

I always seem to get the same answer.

[ArkM]

Excellently: now we have a forum where Salem (not gregorynoob) training his talents for algorithmes design...
Also we have empty slogan: "We only give homework help to those who show effort"...

[gregorynoob]

well okay if this post has caused that much trouble for you ArkM, call a mod to remove it, i don't care really. And thanks for help to Vernon and Salem.

[gregorynoob]

Ok, so i've found the possibly best solution to the problem using recursion with memoization... in case someone wants the code, here it is:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 1000

int X, Y;
int map[ MAX ][ MAX ];
int memo[ MAX ][ MAX ];

int rec( int x, int y ) {
    if( x < X-1 && y < Y-1 ) {
        int r1 = 0, r2 = 0;
        if( memo[x+1][y] )r1 = memo[x+1][y]; else r1 = rec( x+1, y );
        if( memo[x][y+1] )r2 = memo[x][y+1]; else r2 = rec( x, y+1 );
        memo[x][y] = std::max( map[x][y] + r1, map[x][y] + r2 );
        return memo[x][y];
    }
    else if( x < X-1 ) {
         int r1 = 0;
         if( memo[x+1][y] )r1 = memo[x+1][y]; else r1 = rec( x+1, y );
         memo[x][y] = ( map[x][y] + r1 );
         return memo[x][y];
    }
    else if( y < Y-1 ) {
         int r1 = 0;
         if( memo[x][y+1] )r1 = memo[x][y+1]; else r1 = rec( x, y+1 );
         memo[x][y] = ( map[x][y] + r1 );
         return memo[x][y];
    }
    else return map[x][y];
}

int main( void )
{
    memset( memo, 0, sizeof memo );
    scanf( "%d%d", &X, &Y );
    for( int i = 0; i < X; ++i )
         for( int j = 0; j < Y; ++j )
              scanf( "%d", &map[i][j] );
    
    printf( "%d\n", rec( 0, 0 ) );
    
    return 0;
}

and it doesn't use 3 matrixes...
this is an example of...top-down dynamic programming (i guess, think it's called that way in Sedgewick's book) so it recursively computes the largest amount that can be achieved on the way to the X, Y coordinate.
It uses another matrix to memoize the values so they don't have to be computed all over again!