<p>You are given a <code>rows x cols</code> matrix <code>grid</code> representing a field of cherries where <code>grid[i][j]</code> represents the number of cherries that you can collect from the <code>(i, j)</code> cell.</p>

<p>You have two robots that can collect cherries for you:</p>

<ul>
	<li><strong>Robot #1</strong> is located at the <strong>top-left corner</strong> <code>(0, 0)</code>, and</li>
	<li><strong>Robot #2</strong> is located at the <strong>top-right corner</strong> <code>(0, cols - 1)</code>.</li>
</ul>

<p>Return <em>the maximum number of cherries collection using both robots by following the rules below</em>:</p>

<ul>
	<li>From a cell <code>(i, j)</code>, robots can move to cell <code>(i + 1, j - 1)</code>, <code>(i + 1, j)</code>, or <code>(i + 1, j + 1)</code>.</li>
	<li>When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.</li>
	<li>When both robots stay in the same cell, only one takes the cherries.</li>
	<li>Both robots cannot move outside of the grid at any moment.</li>
	<li>Both robots should reach the bottom row in <code>grid</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/29/sample_1_1802.png" style="width: 374px; height: 501px;" />
<pre>
<strong>Input:</strong> grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
<strong>Output:</strong> 24
<strong>Explanation:</strong> Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/sample_2_1802.png" style="width: 500px; height: 452px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
<strong>Output:</strong> 28
<strong>Explanation:</strong> Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>rows == grid.length</code></li>
	<li><code>cols == grid[i].length</code></li>
	<li><code>2 &lt;= rows, cols &lt;= 70</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 100</code></li>
</ul>

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        // Disable synchronization between C and C++ standard streams for faster I/O
        ios_base::sync_with_stdio(false);
        // Untie cin and cout from each other to prevent flushes on cin/cout calls
        cin.tie(nullptr);
        cout.tie(nullptr);

        // Get the number of rows (m) and columns (n) in the grid
        int rows = grid.size(), cols = grid[0].size();

        // Initialize a 2D array dp with size [cols][cols] and set all values to 0
        int dp[cols][cols];
        memset(dp, 0, sizeof(dp));

        // Iterate from the bottom row to the top row of the grid
        for (int row = rows - 1; row >= 0; row--) {
            // Initialize a temporary 2D array next with size [cols][cols] and set all values to -1
            int next[cols][cols];
            memset(next, -1, sizeof(next));

            // Iterate through the first robot's column choices
            for (int col1 = 0; col1 < cols - 1; col1++) {
                // Iterate through the second robot's column choices (must be different from col1)
                for (int col2 = col1 + 1; col2 < cols; col2++) {
                    int maxCherries = 0; // Initialize maxCherries for the current state
                    int currentCherries = grid[row][col1] + grid[row][col2]; // Collect cherries from both robots' positions

                    // Iterate through the possible movements for both robots (left, stay, right)
                    for (int move1 = -1; move1 <= 1; move1++) {
                        for (int move2 = -1; move2 <= 1; move2++) {
                            int newCol1 = col1 + move1, newCol2 = col2 + move2;

                            // Check if the new columns are within bounds and not the same
                            if (newCol1 < 0 || newCol2 >= cols || newCol1 == newCol2) continue;

                            // Update maxCherries with the best option from the previous row
                            maxCherries = max(maxCherries, currentCherries + dp[newCol1][newCol2]);
                        }
                    }

                    // Store the maximum cherries collected for the current state in the next array
                    next[col1][col2] = maxCherries;
                }
            }

            // Copy the contents of next into dp for the next iteration
            memcpy(dp, next, sizeof(next));
        }

        // Return the maximum cherries collected starting from the top row
        return dp[0][cols - 1];
    }
};

11492