Thursday, February 16, 2012

LightOJ 1071 - Baker Vai

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

Problem in short -
Given an x n grid of numbers, you have move 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.

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 <stdio.h>
#include <string.h>
#include <stdlib.h>

#define rep(i,n) for(i=0;i<(n);i++)
#define max(a,b) (((a)>(b))?(a):(b))
#define MAXN 105

int n, m;
int a[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][3];

int go(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];
 
 int &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, go(row, c1+1, c2, 0) + a[row][c1+1]);
  res = max(res, go(row, c1, c2, 1)); //finished moving
 }
 else if(nextMove == 1) { //move the right one to the right
  if(c2+1 < m) res = max(res, go(row, c1, c2+1, 1) + a[row][c2+1]);
  if(c2 > c1) res = max(res, go(row, c1, c2, 2)); //finished moving
 }
 else { //move both to the immediate bottom row
  if(c1 < c2 && row+1 < n) res = max(res, go(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;
 scanf(" %d",&T);
 while(T--) {
  scanf(" %d %d",&n,&m);
  rep(i,n) rep(j,m) scanf(" %d",&a[i][j]);
  printf("Case %d: ",kase++);
  memset(dp, -1, sizeof(dp));
  res = go(0, 0, 0, 1) + a[0][0];
  printf("%d\n",res);
 }
 return 0;
}

4 comments:

  1. Thanks, Sabbir for your this tutorial.

    One point I wanted to mention. I see that you solve the problem using DP (dynamic programming). In addition to giving the code directly (or instead of that), why don't you give the functional relationship used in your solution? I mean the mathematical relation (possibly a recurrence equation) in terms of states you defined, such as how a new state is derived from earlier states and how states got changed. That presentation seems to be more important and more intuitive than seeing the code itself in understanding the problem and its solution.

    I appreciate your efforts. Please keep it up.
    Thanks.

    ReplyDelete
  2. A good explanation is written in here http://lbv-pc.blogspot.com/2012/07/baker-vai.html

    ReplyDelete