Problem in short -

Given anmxngrid 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 -

- Current row
- Current column of left path
- Current column of right path
- Current move

Here move can be of 3 types -

- Moving the left path one cell to the east
- Moving the right path once cell to the east
- 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; }

Thanks, Sabbir for your this tutorial.

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

good question

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

ReplyDeletehere

ReplyDelete