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

int desync = []{
    ios::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();
struct Robot_format {
  int P_R1;
  int P_R2;
  int sum;
  Robot_format() : P_R1(), P_R2(), sum() {}
  Robot_format(int x, int y, int z) : P_R1(x), P_R2(y), sum(z) {}
};
class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        queue<Robot_format> vals;
        vector<vector<vector<int>>> positions(grid.size(), vector<vector<int>>(grid[0].size(), vector<int>(grid[0].size(),-1)));
        vals.push(Robot_format(0, grid[0].size()-1, grid[0][0] + grid[0][grid[0].size()-1]));
        positions[0][0][grid[0].size()-1] = grid[0][0] + grid[0][grid[0].size()-1];
        for (int row = 1; row != grid.size(); row++) {
            for (int i = vals.size(); i > 0; i--, vals.pop()) {
                if (vals.front().sum < positions[row-1][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)]) {
                    continue;
                }
                int x = vals.front().sum + grid[row][vals.front().P_R1] + (vals.front().P_R1 != vals.front().P_R2 ? grid[row][vals.front().P_R2] : 0);
                if (positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] == -1 || x > positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)]) {
                    vals.push(Robot_format(vals.front().P_R1, vals.front().P_R2, x ) );
                    positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] = x;
                }
                if (vals.front().P_R2 != 0) {
                    vals.front().P_R2--; int x = vals.front().sum + grid[row][vals.front().P_R1] + (vals.front().P_R1 != vals.front().P_R2 ? grid[row][vals.front().P_R2] : 0);
                    if (positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] == -1 || x > positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)]) {
                        vals.push(Robot_format(vals.front().P_R1, vals.front().P_R2, x ) );
                        positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] = x;
                    } vals.front().P_R2++;
                }
                if (vals.front().P_R2 != grid[0].size()-1) {
                    vals.front().P_R2++; int x = vals.front().sum + grid[row][vals.front().P_R1] + (vals.front().P_R1 != vals.front().P_R2 ? grid[row][vals.front().P_R2] : 0);
                    if (positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] == -1 || x > positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)]) {
                        vals.push(Robot_format(vals.front().P_R1, vals.front().P_R2, x ) );
                        positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] = x;
                    } vals.front().P_R2--;
                }
                if (vals.front().P_R1 != 0) {
                    vals.front().P_R1--; int x = vals.front().sum + grid[row][vals.front().P_R1] + (vals.front().P_R1 != vals.front().P_R2 ? grid[row][vals.front().P_R2] : 0);
                    if (positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] == -1 || x > positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)]) {
                        vals.push(Robot_format(vals.front().P_R1, vals.front().P_R2, x ) );
                        positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] = x;
                    }
                    if (vals.front().P_R2 != 0) {
                        vals.front().P_R2--; int x = vals.front().sum + grid[row][vals.front().P_R1] + (vals.front().P_R1 != vals.front().P_R2 ? grid[row][vals.front().P_R2] : 0);
                        if (positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] == -1 || x > positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)]) {
                            vals.push(Robot_format(vals.front().P_R1, vals.front().P_R2, x ) );
                            positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] = x;
                        } vals.front().P_R2++;
                    }
                    if (vals.front().P_R2 != grid[0].size()-1) {
                        vals.front().P_R2++; int x = vals.front().sum + grid[row][vals.front().P_R1] + (vals.front().P_R1 != vals.front().P_R2 ? grid[row][vals.front().P_R2] : 0);
                        if (positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] == -1 || x > positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)]) {
                            vals.push(Robot_format(vals.front().P_R1, vals.front().P_R2, x ) );
                            positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] = x;
                        } vals.front().P_R2--;
                    } vals.front().P_R1++;
                }
                if (vals.front().P_R1 != grid[0].size()-1) {
                    vals.front().P_R1++; int x = vals.front().sum + grid[row][vals.front().P_R1] + (vals.front().P_R1 != vals.front().P_R2 ? grid[row][vals.front().P_R2] : 0);
                    if (positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] == -1 || x > positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)]) {
                        vals.push(Robot_format(vals.front().P_R1, vals.front().P_R2, x ) );
                        positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] = x;
                    }
                    if (vals.front().P_R2 != 0) {
                        vals.front().P_R2--; int x = vals.front().sum + grid[row][vals.front().P_R1] + (vals.front().P_R1 != vals.front().P_R2 ? grid[row][vals.front().P_R2] : 0);
                        if (positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] == -1 || x > positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)]) {
                            vals.push(Robot_format(vals.front().P_R1, vals.front().P_R2, x ) );
                            positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] = x;
                        } vals.front().P_R2++;
                    }
                    if (vals.front().P_R2 != grid[0].size()-1) {
                        vals.front().P_R2++; int x = vals.front().sum + grid[row][vals.front().P_R1] + (vals.front().P_R1 != vals.front().P_R2 ? grid[row][vals.front().P_R2] : 0);
                        if (positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] == -1 || x > positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)]) {
                            vals.push(Robot_format(vals.front().P_R1, vals.front().P_R2, x ) );
                            positions[row][min(vals.front().P_R1,vals.front().P_R2)][max(vals.front().P_R1,vals.front().P_R2)] = x;
                        } vals.front().P_R2--;
                    } vals.front().P_R1--;
                }
            }
        }
        int max_val = 0;
        for (; vals.size() != 0; vals.pop()) {
            max_val = max(max_val, vals.front().sum);
        }
        return max_val;
    }
};
26107