1218. Cherry Pickup I — Two-Pass DP

Given an n x n grid with 1 (cherry), 0 (empty), and -1 (thorn), travel from the top-left to the bottom-right moving right or down, then back to the top-left moving left or up, collecting cherries (each cell yields its cherry only once). Return the maximum cherries collected, or 0 if the round trip is impossible. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the maximum cherries collected.

Examples

Input: {"grid":[[0,1,-1],[1,0,-1],[1,1,1]]}
Output: 5
Explanation: Two passes collect five cherries.

Input: {"grid":[[1,1,-1],[1,-1,1],[-1,1,1]]}
Output: 0
Explanation: No valid round trip.

Input: {"grid":[[1]]}
Output: 1
Explanation: Single cherry.

Constraints

• 1<=n<=50

Asked by