Grid game

[roshan95]

You are given a square grid of positive and negative numbers. You have to start at the top left corner of the grid and find a path to the bottom-right corner. In each step, you are only allowed to move one position to the right or one position down. As a special bonus, you are allowed at most one move that can be either to the left or up. Note that you are allowed to visit a position more than once as a result of this special move.

Your aim is to find such a path that has the maximum weight, where the weight of a path is the sum of all the numbers visited along the path.
Input format

The first line of the input contains one integer N, the number of rows and columns in the grid. Lines 2 to N+1 describe the N rows of the grid. Each of these N lines of input consists of N space separated integers, corresponding to the numbers in one row.
Notes

In all cases, N ≤ 2000. Each number in the grid is guaranteed to be less than 1000.
Output format

Your output should be a single line consisting of one integer, the sum of the values on the path of maximum weight.
Sample Input

4
12 -16 10 -12
-16 13 -14 7
7 -4 16 -15
-7 16 -9 8

Sample Output

32

[Zhuge]

lol @ copy & pasted homework assignment. What do you want us to do about it?

[roshan95]

not a homework assignment...supposed to be an old olympiad question

[Browni3141]

The easiest way, but probably not the fastest would be to test every path and use variables to store the best path and weight. Try to get a program to do this and work from there. Post whatever you have so far.

Also, what is the olympiad?

[roshan95]

i tried that...but there seem to be millions of combinations....
thanks for your effort...it was for the zonal computing olympiad

[Browni3141]

Do you have a code for it? If so then post it.

[Disch]

Fun problem.

My approach:

make an NxN grid. Each cell in the grid has 3 values:

- a weight, obviously (W)
- highest weight without taking the bonus move (A)
- highest weight with taking the bonus move (B)

LUDR are neighboring cells. ie: LA would be the highest possible weight for the cell left of the current cell without taking the bonus move.

X is the current cell. ie: XW is the current cell's weight.


XA = the highest of:
.. LA + XW
.. UA + XW

XB = the highest of:
.. LB + XW
.. UB + XW
.. RA + XW
.. DA + XW


Calculate the A set first in "read like a book" order (top to bottom, left to right)

Once set A is calculated, calculate set B in the same order.


Once all sets have been calculated, the solution is A or B (whichever is greater) of the bottom right most cell. If you use set A it means there was no advantageous way to use the bonus move.


EDIT:

If you want to record the path (like to draw the best path from beginning to end instead of just showing the best weight), you could keep some more info in each cell to indicate which option was used to calculate XA and XB.

Then mapping it would just be tracking backwards from the lower right corner.

[Disch]

I was bored. Here's a program I whipped up that appears to work. There's room for optimization and it's not very expandable:

#include <iostream>
#include <limits>
#include <algorithm>
#include <string>

//================================
//  I don't want to mess with I/O .. so hardcoded values

static const int gridSize = 4;
static const int weights[gridSize][gridSize] = {
    { 12,-16, 10,-12 },
    {-16, 13,-14,  7 },
    {  7, -4, 16,-15 },
    { -7, 16, -9,  8 }
};


//=================================

enum Direction
{
    Up     = 0,
    Left,
    Down,
    Right,
    None
};

struct Cell
{
    // weight stored separately in weights[][]
    int A;
    int B;
    Direction pathA;    // directs towards the previous cell in the chain
    Direction pathB;    //  so basically it's backwards from the best path
};

//===================================
//  globals because I'm lazy

Cell grid[gridSize][gridSize];

//==========================================
//==========================================


void CalculateSetA()
{
    // special case for cell 0,0
    grid[0][0].A = weights[0][0];
    grid[0][0].pathA = None;

    //==
    int best;
    Direction bestdir;

    for(int y = 0; y < gridSize; ++y)
    {
        for(int x = !y; x < gridSize; ++x) // funky initialization to skip 0,0
        {
            bestdir = None;
            best = std::numeric_limits<int>::min();

            if(x > 0)
            {
                best = grid[y][x-1].A;
                bestdir = Left;
            }
            if((y > 0) && (grid[y-1][x].A > best))
            {
                best = grid[y-1][x].A;
                bestdir = Up;
            }

            // apply best
            grid[y][x].A = best + weights[y][x];
            grid[y][x].pathA = bestdir;
        }
    }
}


void CalculateSetB()
{
    int best;
    Direction bestdir;

    for(int y = 0; y < gridSize; ++y)
    {
        for(int x = 0; x < gridSize; ++x)
        {
            bestdir = None;
            best = std::numeric_limits<int>::min();

            if(x > 0)
            {
                best = grid[y][x-1].B;
                bestdir = Left;
            }
            if((y > 0) && (grid[y-1][x].B > best))
            {
                best = grid[y-1][x].B;
                bestdir = Up;
            }
            if((x < gridSize-1) && (grid[y][x+1].A > best))
            {
                best = grid[y][x+1].A;
                bestdir = Right;
            }
            if((y < gridSize-1) && (grid[y+1][x].A > best))
            {
                best = grid[y+1][x].A;
                bestdir = Down;
            }

            // apply best
            grid[y][x].B = best + weights[y][x];
            grid[y][x].pathB = bestdir;
        }
    }
}

//=======================================================

std::string GetBestPathString()
{
    std::string path;

    int y, x;
    y = x = gridSize - 1;

    bool onB = grid[y][x].B > grid[y][x].A;

    bool go = true;
    while(go)
    {
        switch(onB ? grid[y][x].pathB : grid[y][x].pathA)
        {
        case Left:
            --x;
            path += 'R';
            break;
        case Up:
            --y;
            path += 'D';
            break;
        case Right:
            ++x;
            path += 'L';
            onB = false;
            break;
        case Down:
            ++y;
            path += 'U';
            onB = false;
            break;
        case None:
            go = false;
            break;

        default:
            throw "WTF";
        }
    }

    std::reverse(path.begin(),path.end());
    return path;
}


int main()
{
    CalculateSetA();
    CalculateSetB();

    const Cell& c = grid[gridSize-1][gridSize-1];

    bool usedbonus = c.B > c.A;
    std::cout << "The best weight is:  " << std::max(c.B,c.A);

    std::cout << "\nThe bonus move was ";
        if(!usedbonus) std::cout << "not ";
    std::cout << "used.";

    std::cout << "\nThe best path is:\n" << GetBestPathString();
    std::cout << std::endl;

    std::cin.get();
}

EDIT:

I wrote this under a hardcoded assumption that there is only 1 bonus move, but it occurs to me that this could easily be written to handle any number of bonus moves. Each additional bonus move would just require another pass over the grid to calculate the new set.

This is definitely faster than the brute force "check every possible path and see which is the best" approach, but I'm not convinced it's the fasted possible solution.

I wonder if anyone else is still thinking about this or if it's just me =P


I should go to bed.