Baker Vai - LightOJ 1071

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1071

Problem Name: Baker Vai

LightOJ ID: 1071

Problem in short –

    Given an m x n grid of numbers, you have moved from top-left cell to the bottom-right cell and then get back to top-left cell without stepping on any cell twice and maximizing the sum of the numbers on the path.

The problem asks for the maximum sum possible when moving inside a matrix of integers of size m×nm×n. You start on the top-left corner, and moving only down or right you have to reach the bottom-right corner, and then go back to where you started, moving only up or left. In addition, you can’t step on any cell more than once, except for the point where you started.

Now, we can think of this problem as finding 2 separate paths (that doesn't cross each other) from top-left to bottom right while moving only to east or south. My dp solution proceeds row by row and keeps track of 4 states -

1. Current row
2. Current column of left path
3. Current column of right path
4. Current move

Here move can be of 3 types - 

1. Moving the left path one cell to the east
2. Moving the right path once cell to the east
3. Moving both the path once cell to the south

Here’s the source code :

#include<bits/stdc++.h>

#define rep(i,n) for(i=0; i<n; i++)

#define max(a,b) (((a)>(b))?(a):(b))

#define MAX 105

using namespace std;

int n, m;

long a[MAX][MAX];

long dp[MAX][MAX][MAX][3];

int turn(int row, int c1, int c2, int nextMove)

{

    if(row == n-1 && c2 == m-1 && c1 == m-2 && nextMove == 0)

        return 0;

    if(dp[row][c1][c2][nextMove] != -1)

        return dp[row][c1][c2][nextMove];

    long &res = dp[row][c1][c2][nextMove];

    res = 0;

    if(nextMove == 0)

    { //move the left one to the right

        if(c1+1 < c2) res = max(res, turn(row, c1+1, c2, 0) + a[row][c1+1]);

            res = max(res, turn(row, c1, c2, 1));

    }

    else if(nextMove == 1)

    { //move the right one to the right

        if(c2+1 < m)

            res = max(res, turn(row, c1, c2+1, 1) + a[row][c2+1]);

        if(c2 > c1)

            res = max(res, turn(row, c1, c2, 2));

    }

    else

    { //move both to the immediate bottom row

        if(c1 < c2 && row+1 < n)

            res = max(res, turn(row+1, c1, c2, 0) + a[row+1][c1] + a[row+1][c2]);

    }

    return res;

}

int main()

{

    int T, kase=1, i, j;

    int res;

    cin >> T;

    while(T--)

    {

    cin >> n >> m;

    //rep(i,n) rep(j,m) cin >> a;

    rep(i,n) rep(j,m) scanf(" %ld",&a[i][j]);

    cout << "Case " <<kase++ <<": ";

    memset(dp, -1, sizeof(dp));

    res = turn(0, 0, 0, 1) + a[0][0];

    cout << res <<endl;

    }

    return 0;

}