#2017
Grid Game
specialist · 700 · lc medium +30 · verified · 60.9% accepted · 1,807 likes · top 60%
Description
In a 2 x n grid where each cell (r, c) holds some points, two robots both travel from (0, 0) to (1, n-1) (each may only move right or down). Robot 1 goes first, collecting points and zeroing its path. Robot 2 then goes, collecting remaining points. Robot 1 plays to minimize Robot 2's score; Robot 2 plays to maximize its own score. Both play optimally. Return the score Robot 2 collects.
Example 1:
Input: grid = [[2,5,4],[1,5,1]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 0 + 4 + 0 = 4 points.
Example 2:
Input: grid = [[3,3,1],[8,5,2]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 3 + 1 + 0 = 4 points.
Example 3:
Input: grid = [[1,3,1,15],[1,3,3,1]]
Output: 7
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 1 + 3 + 3 + 0 = 7 points.
Code
1
2
3