#include <iostream>
#include <vector>

using std::vector;

using std::cout; using std::endl;

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        int dp[2 * n - 1][n][n];
        memset(dp, 0xFF, sizeof(dp));
        dp[2 * n - 2][n - 1][n - 1] = 0;
        dp[0][0][0] = grid[0][0];
        for (int k = 1; k < 2 * n - 1; k++) {
            for (int x1 = 0; x1 <= k && x1 < n; x1++) {
                for (int x2 = 0; x2 <= k && x2 < n; x2++) {
                    int y1 = k - x1, y2 = k - x2;
                    // current coordinate is rock
                    if (grid[x1][y1] == -1 || grid[x2][y2] == -1) continue;
                    for (int i = 0; i < 4; i++) {
                        int x1_ = x1 + dx1[i], x2_ = x2 + dx2[i];
                        int y1_ = k - 1 - x1_, y2_ = k - 1 - x2_;
                        // previous coordinate is not valid
                        if (x1_ < 0 || x2_ < 0 || y1_ < 0 || y2_ < 0) continue;
                        // previous coordinate is rock
                        if (grid[x1_][y1_] == -1 || grid[x2_][y2_] == -1) continue;
                        // previous state is not reachable
                        if (dp[k - 1][x1_][x2_] == -1) continue;
                        int delta = x1 == x2 ? grid[x1][y1] : grid[x1][y1] + grid[x2][y2];
                        dp[k][x1][x2] = std::max(dp[k][x1][x2], dp[k - 1][x1_][x2_] + delta);
                    }
                }
            }
        }
        return dp[2 * n - 2][n - 1][n - 1];
    }

private:
    int dx1[4] = {0, -1, 0, -1};
    int dx2[4] = {0, 0, -1, -1};
};

// (0, 0) -> (n - 1, n - 1) -> (0, 0) == (0, 0) -> (n - 1, n - 1) 2 times == 2 people start at (0, 0) at the same time
// dp[k][x1][x2] means max cherries from (0, 0) to (x1, y1) and (x2, y2) at k steps
// dp[0][0][0] = grid[0][0]
// dp[k][x1][x2] = max(dp[k - 1][x1][x2] + delta, dp[k - 1][x1 - 1][x2] + delta, dp[k - 1][x1][x2 - 1] + delta, dp[k - 1][x1 - 1][x2 - 1] + delta)

int main() {
    Solution* sol = new Solution();

    vector<vector<int>> grid = {{0, 1, -1}, {1, 0, -1}, {1, 1, 1}};
    cout << "actual: " << sol->cherryPickup(grid) << ", expected: " << 5 << endl;

    grid = {{1, 1, -1}, {1, -1, 1}, {-1, 1, 1}};
    cout << "actual: " << sol->cherryPickup(grid) << ", expected: " << 0 << endl;

    return 0;
}