Analysis of GESP C++ Level 4 Exam Questions – Strategic Deployment (luogu-B4415)

GESP C++ Level 4 exam questions from September 2025, focusing on two-dimensional arrays, difficulty ⭐⭐★☆☆.

• GESP Level 1 Practice Questions List

• GESP Level 1 Exam Questions List

• GESP Level 2 Practice Questions List

• GESP Level 2 Exam Questions List

• GESP Level 3 Practice Questions List

• GESP Level 3 Exam Questions List

• GESP Level 4 Practice Questions List

• GESP Level 4 Exam Questions List

• GESP Level 1-5 Syllabus Analysis

• Essential Skills for GESP/CSP Programming

luogu-B4415 [GESP202509 Level 4] Strategic Deployment

Problem Requirements

Problem Description

As a general, you naturally need to deploy your troops strategically. The map can be viewed as a grid of rows and columns, where suitable grids for deployment are marked with 1, and unsuitable grids are marked with 0. You need to select a rectangular area on the map for deployment, which must not contain any unsuitable grids. What is the maximum number of grids that can be included in the selected rectangular area?

Input Format

The first line contains two positive integers, representing the number of rows and columns of the map grid.

Next, rows, each containing integers, indicating whether each grid in the row is suitable for deployment.

Output Format

One line, containing an integer that represents the maximum number of grids in the suitable rectangular area for deployment.

Input/Output Example #1

Input #1

4 3
0 1 1
1 0 1
0 1 1
1 1 1

Output #1

4

Input/Output Example #2

Input #2

3 5
1 0 1 0 1
0 1 0 1 0
0 1 1 1 0

Output #2

3

Notes/Tips

For all test cases, it is guaranteed that .

Problem Analysis

Given a 0/1 matrix, find the maximum rectangular area composed entirely of 1s . Since , a brute force enumeration can be directly applied, or prefix sums can be used for optimization.

Approach 1: Six Nested Loops for Pure Brute Force

1. Use four nested loops to enumerate the top-left and bottom-right corners of the rectangle, where .
2. For each rectangle, use two nested loops to scan its interior:

• If any is found, immediately prune and abandon that rectangle;
• If all are 1s, then the area is updated.

The time complexity is when , which is acceptable.

Approach 2: Two-Dimensional Prefix Sum Optimization

1. Preprocess the two-dimensional prefix sum array, which can be completed in .
2. Still use four nested loops to enumerate the rectangle, but use the prefix sum formula to calculate the area:
3. If , it indicates that the rectangle is entirely composed of 1s, and the answer is updated.
4. The time complexity is when , which is more stable.

Both implementations can pass the GESP Level 4 data range.

Example Code

Method 1: Brute Force Simulation with 6 Nested Loops

#include <iostream>

int num_ary[15][15]; // Store the map: 1 indicates suitable for deployment, 0 indicates unsuitable for deployment
int main() {
    int n, m;
    std::cin >> n >> m; // Read the number of rows n and columns m
    // Read the map data
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> num_ary[i][j];
        }
    }

    int max_count = 0; // Record the number of grids in the largest valid rectangle

    // Enumerate the top-left corner of the rectangle (i,j)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // Enumerate the bottom-right corner of the rectangle (k,l), requiring k≥i, l≥j
            for (int k = i; k < n; k++) {
                for (int l = j; l < m; l++) {
                    int count = 0;    // Number of 1s in the current rectangle
                    bool allOne = true; // Assume the current rectangle is all 1s

                    // Check if the interior of the rectangle is all 1s
                    for (int x = i; x <= k; x++) {
                        for (int y = j; y <= l; y++) {
                            if (num_ary[x][y] == 1) {
                                count++; // Count the number of 1s
                            } else {
                                allOne = false; // Found a 0, mark as invalid
                                count = 0;        // Area resets to zero
                                break;            // Exit the inner loop early
                            }
                        }
                        if (!allOne) {
                            break; // Exit the outer loop early
                        }
                    }

                    // If the rectangle is valid, try to update the answer
                    if (allOne) {
                        max_count = std::max(max_count, count);
                    }
                }
            }
        }
    }

    std::cout << max_count << std::endl; // Output the maximum number of grids
    return 0;
}

Method 2: Prefix Sum with 4 Nested Loops

#include <iostream>

// Store the map: 1 indicates suitable for deployment, 0 indicates unsuitable for deployment
int num_ary[15][15];
// Store the two-dimensional prefix sum, sum_ary[i][j] indicates the sum of all elements from (1,1) to (i,j)
int sum_ary[15][15];
int main() {
    int n, m;
    std::cin >> n >> m; // Read the number of rows n and columns m
    
    // Read the map data and simultaneously calculate the two-dimensional prefix sum
    // Note: Here the index starts from 1 for easier prefix sum calculation
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> num_ary[i][j];
            // Two-dimensional prefix sum calculation formula: current cell = upper cell + left cell - upper left cell (to avoid duplication) + current value
            sum_ary[i][j] = sum_ary[i - 1][j] + sum_ary[i][j - 1] - sum_ary[i - 1][j - 1] + num_ary[i][j];
        }
    }
    
    int max_count = 0; // Record the number of grids in the largest valid rectangle
    
    // Enumerate the top-left corner of the rectangle (i,j)
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // Enumerate the bottom-right corner of the rectangle (k,l), requiring k≥i, l≥j
            for (int k = i; k <= n; k++) {
                for (int l = j; l <= m; l++) {
                    // Use the two-dimensional prefix sum formula to calculate the sum of the submatrix from (i,j) to (k,l)
                    // Formula: sum(i,j,k,l) = sum[k][l] - sum[k][j-1] - sum[i-1][l] + sum[i-1][j-1]
                    int temp_sum = sum_ary[k][l] - sum_ary[k][j - 1] - sum_ary[i - 1][l] + sum_ary[i - 1][j - 1];
                    
                    // Rectangle area = number of rows * number of columns = (k-i+1) * (l-j+1)
                    // If the sum of elements equals the rectangle area, it indicates that the rectangle is all 1s (each cell is 1)
                    if (temp_sum == (k - i + 1) * (l - j + 1)) {
                        // Update the area of the largest valid rectangle
                        max_count = std::max(max_count, temp_sum);
                    }
                }
            }
        }
    }

    std::cout << max_count << std::endl; // Output the maximum number of grids
    return 0;
}

For detailed information on GESP levels, exam questions explanations, knowledge expansion, and practice lists, see:

[Pinned] [GESP] C++ Certification Learning Resource Compilation

“luogu-” series problems can be evaluated online at Luogu Problem Bank.

“bcqm-” series problems can be evaluated online at Programming Enlightenment Problem Bank.