Problem Involving Grids - 4

Problem statement

Let’s discuss one more complex problem based on grids. It is another variant of the grid problems that we discussed earlier. The problem statement is given below. You are given a 2-D matrix A of n rows and m columns where A[i][j] denotes the calories burnt. Two persons, a boy and a girl start from two corners of this matrix. The boy starts from the cell (1, 1) and needs to reach the cell (n, m). On the other hand, the girl starts from the cell (n, 1) and needs to reach (1, m). The boy can move right and down. The girl can move right and up. As they visit a cell, the amount in the cell A[i][j] is added to their total of calories burnt. You have to maximize the sum of total calories burnt by both of them under the condition that they shall meet only in one cell and the cost of this cell shall not be included in either of their totals.

Solution: Dynamic programming approach

Let us analyze this problem in steps:

• The boy can meet the girl in only one cell. Let’s assume they meet at cell (i, j).
• The boy can come in from the left or the top, i.e., (i, j-1) or (i-1, j). He can move right or down. The sequence for the boy can be:

  (i, j-1) —> (i, j) —> (i, j+1)
  (i, j-1) —> (i, j) —> (i+1, 1)
  (i-1, j) —> (i, j) —> (i, j+1)
  (i-1, j) —> (i, j) —> (i+1, j)
  

• Similarly, the girl can come in from the left or bottom, i.e., (i, j-1) or (i+1, j) and she can go up or right. The sequence for the girl’s movement can be:

  (i, j-1) —> (i, j) —> (i, j+1)
  (i, j-1) —> (i, j) —> (i-1, j)
  (i+1, j) —> (i, j) —> (i, j+1)
  (i+1, j) —> (i, j) —> (i-1, j)
  

• Comparing the 4 sequences of the boy and the girl, the boy and girl meet only at one position (i, j) if and only if:

  Boy: (i, j-1) —> (i, j) —>(i, j+1) 
  Girl: (i+1, j) —> (i, j) —>(i-1, j)
  

  or

  Boy: (i-1, j) —> (i, j) —>(i+1, j) 
  Girl: (i, j-1) —> (i, j) —>(i, j+1)
  

• Now, we can solve the problem by creating 4 tables:
  • Boy’s journey from (1, 1) to meeting cell (i, j).
  • Boy’s journey from meeting cell (i, j) to end (n, m).
  • Girl’s journey from start (n, 1) to meeting cell (i, j).
  • Girl’s journey from meeting cell (i, j) to end (1, n)
• The meeting cell can range from 2 <= i <= n - 1 and 2 <= j <= m - 1.

Let’s now move on to the implementation to better understand the logic that we discussed above.