2017. Grid Game | zhengxingxing

Method 1

You are given a 0-indexed 2D array grid of size 2 x n, where grid[r][c] represents the number of points at position (r, c) on the matrix. Two robots are playing a game on this matrix.
Both robots initially start at (0, 0) and want to reach (1, n-1). Each robot may only move to the right ((r, c) to (r, c + 1)) or down ((r, c) to (r + 1, c)).
At the start of the game, the first robot moves from (0, 0) to (1, n-1), collecting all the points from the cells on its path. For all cells (r, c) traversed on the path, grid[r][c] is set to 0. Then, the second robot moves from (0, 0) to (1, n-1), collecting the points on its path. Note that their paths may intersect with one another.
The first robot wants to minimize the number of points collected by the second robot. In contrast, the second robot wants to maximize the number of points it collects. If both robots play optimally, return the number of points collected by the second robot.

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.

Method 1

【O(n) time | O(n) space】

package Leetcode.Math;

/**
 * @author zhengxingxing
 * @date 2025/01/21
 */
public class GridGame {
    public static long gridGame(int[][] grid) {
        // Length of each row in the grid
        int n = grid[0].length;

        // Prefix sum arrays for efficient range sum calculations
        // preSum1: prefix sums for top row
        // preSum2: prefix sums for bottom row
        long[] preSum1 = new long[n + 1];
        long[] preSum2 = new long[n + 1];

        // Calculate prefix sums for both rows
        // This allows O(1) time range sum queries
        for (int i = 0; i < n; i++) {
            preSum1[i + 1] = preSum1[i] + grid[0][i];
            preSum2[i + 1] = preSum2[i] + grid[1][i];
        }

        // Initialize answer with maximum possible value
        // We will minimize this value as we find better solutions
        long ans = Long.MAX_VALUE;

        // Try each possible turning point for Robot 1
        // For each column i, calculate the maximum points Robot 2 can get
        for (int i = 0; i < n; i++) {
            // Calculate remaining points in top row after column i
            // This represents one possible path for Robot 2
            long top = preSum1[n] - preSum1[i + 1];

            // Calculate points in bottom row before column i
            // This represents another possible path for Robot 2
            long bottom = preSum2[i];

            // Robot 2 will choose the path with maximum points
            long secondRobot = Math.max(top, bottom);

            // Update answer if this is the smallest maximum we've found
            // We want to minimize the maximum points Robot 2 can get
            ans = Math.min(ans, secondRobot);
        }

        // Return the minimum possible maximum points for Robot 2
        return ans;
    }

    // 主方法，包含测试用例
    public static void main(String[] args) {
        // Test Case 1: Basic example
        // Grid: [ [2,5,4],
        //        [1,5,1] ]
        // Expected output: 4
        int[][] grid1 = { { 2,5,4}, {1,5,1 } };
        System.out.println("Test Case 1 Result: " + gridGame(grid1));

        //Additional test cases can be uncommented for further testing
        // Test Case 2
        int[][] grid2 = { { 3,3,1}, {8,5,2 } };
        System.out.println("Test Case 2 Result: " + gridGame(grid2));

        // Test Case 3
        int[][] grid3 = { { 1,3,1,15}, {1,3,3,1 } };
        System.out.println("Test Case 3 Result: " + gridGame(grid3));

        // Test Case 4: More complex example
        int[][] grid4 = { { 20,3,20,17,2,12,15,17,4,15},
                        {20,10,13,14,15,5,2,3,14,3 } };
        System.out.println("Test Case 4 Result: " + gridGame(grid4));

    }
}

Method 1

Enjoy Reading This Article?