Sunday, July 3, 2011

Collecting Apples

Problem: The original problem is from TopCoder. Given a M*N matrix, in each cell, there are a number of apples. When you visit one cell, you can grab the apple away. You make three passes to collect apples. In the first pass, you start from top-left,  go either right or down until reading bottom-right. In the second pass, you start from bottom-right, go either up or left until reading top-left. In the third pass, you go from top-left to bottom-right again. What are the maximum number of apples you can collect?

Solution: This is a DP problem. But first we need to do some reduction to convert the problem to a easier one. If the problem only contains the first pass, it is an easy DP problem.

  • One key observation is the second pass can be reversed so that the problem can be transferred to that three paths starting from top-left to bottom-right.
  • We create a status matrix MAX[][][], MAX[i][j][k] denote at a certain round, the column coordinates of the three paths (you can get the row coordinates from i,j,k and round number x). 
  • From the previous position to current position, at most three cells should be visited. They are (x-i, i), (x-j, j) and (x-k, k). Then we can get the apples at the three cells (remember don't add the duplicate cell). There are multiple ways (2*2*2) to reach these three cells (from up or from left). They we need to leverage the MAX[][][] from previous round to find a previous state to the three cells which can maximize MAX[i][j][k]. 
  • There are totally M+N-2 rounds and after the final round, the answer will be stored in MAX[N-1][N-1][N-1]
The key algorithm is as follow:
    public int mostApples(string[] L) {
    
        int X=L[0].Length, Y=L.Length, XY=X+Y;
        int[,,] best = new int[X,X,X]; 
        int[,,] b2 = new int[X,X,X];     
         
        for (int A=0; A<X; A++) 
        for (int B=0; B<X; B++) 
        for (int C=0; C<X; C++)    
            best[A,B,C] = -999999999;
    
        best[0,0,0] = 0;
    
        for (int t=1; t<=X+Y-2; t++)
        {    
            for (int A=0; A<X; A++) 
            for (int B=0; B<X; B++) 
            for (int C=0; C<X; C++)
            {
               int aa = t-A, bb=t-B, cc=t-C;
               if (aa < 0 || bb < 0 || cc < 0 || aa >= Y || bb >= Y || cc >= Y) continue;
      
               int bestHere = 0;
               int delta = (int)(L[aa][A] - 48);
               
               if (B != A) delta += (int)(L[bb][B] - 48);
               if (C != A && C != B) delta += (int)(L[cc][C] - 48);
     
               if ( A>0 &&  B>0 &&  C>0) bestHere = Max(bestHere, best[A-1, B-1, C-1] + delta);
               if ( A>0 &&  B>0 && cc>0) bestHere = Max(bestHere, best[A-1, B-1, C  ] + delta);
               if ( A>0 && bb>0 &&  C>0) bestHere = Max(bestHere, best[A-1, B,   C-1] + delta);
               if ( A>0 && bb>0 && cc>0) bestHere = Max(bestHere, best[A-1, B,   C  ] + delta);
               if (aa>0 &&  B>0 &&  C>0) bestHere = Max(bestHere, best[A,   B-1, C-1] + delta);
               if (aa>0 &&  B>0 && cc>0) bestHere = Max(bestHere, best[A,   B-1, C  ] + delta);
               if (aa>0 && bb>0 &&  C>0) bestHere = Max(bestHere, best[A,   B,   C-1] + delta);
               if (aa>0 && bb>0 && cc>0) bestHere = Max(bestHere, best[A,   B,   C  ] + delta);
               b2[A,B,C] = bestHere;
             }
     
             int[,,] temp = best; 
             best = b2; 
             b2 = temp;
      }
     
    return best[X-1,X-1,X-1];
    }
    

    No comments:

    Post a Comment