GESP C++ Level 4 Real Exam Questions (2D Arrays) [202409] Black and White Squares (luogu-B4040)

GESP C++ Level 4 real exam questions for September 2024. This problem mainly tests the application of 2D arrays. The brute force difficulty is not high, overall difficulty ⭐⭐★☆☆. This problem is rated as <span>Popular-</span> on Luogu.

GESP Level 1 Practice Questions List
GESP Level 1 Real Exam Questions List
GESP Level 2 Practice Questions List
GESP Level 2 Real Exam Questions List
GESP Level 3 Practice Questions List
GESP Level 3 Real Exam Questions List
GESP Level 4 Practice Questions List
GESP Level 4 Real Exam Questions List
GESP Level 1-5 Syllabus Analysis

luogu-B4040 [GESP202409 Level 4] Black and White Squares

Problem Requirements

Problem Description

Little Yang has a row column grid, where each cell is either white or black. Little Yang wants to know if there exists a subrectangle in the grid that satisfies the following conditions:

The subrectangle consists of rows columns;

The first row and the last row contain only white cells;

For the first row and the last row, only the first and the last cells are white, while the rest are black;

Please write a program to help Little Yang determine this.

Input Format

The first line contains a positive integer , representing the number of test cases. The following are groups of test cases. For each group of test cases, there are a total of rows. The first line contains two positive integers , meaning as described in the problem statement. After that, rows, each containing a string of length , representing the color of the cells in the grid. If it is , then the corresponding cell is white; otherwise, it is black.

Output Format

For each group of test cases, if it exists, output Yes; otherwise, output No.

Input Output Example #1

Input #1

Output #1

No
Yes
No

Explanation/Hint

Example 1 Explanation

Data Scale and Constraints

For all test data, it is guaranteed that ,.

Problem Analysis

The solution approach for this problem is as follows:

The problem requires finding a submatrix in a row column grid that meets specific conditions. The specific requirements are:

The first row and the last row are all white ()
The first row and the last row only have the first column and the last column as white (), while the middle two columns are black ().

Key points for solving the problem:

The size of the submatrix is fixed at , and other sizes do not need to be considered.
It is only necessary to determine if such a submatrix exists, not to count the number.
A brute force enumeration method can be used to traverse all possible top-left positions.

Specific implementation steps:

Read the grid data and store it in a string array.
Traverse all possible top-left positions.
For each position, check if the submatrix with the top-left corner at meets the requirements.
If a satisfying submatrix is found, output “Yes” and terminate.
If no satisfying submatrix is found after traversing all positions, output “No”.

Time Complexity Analysis:

For each test case, it is necessary to traverse all possible top-left positions:
For each position, it is necessary to check the submatrix:
Total time complexity:
Since , the brute force method can completely pass.

Notes:

When checking the submatrix, pay attention to boundary conditions to prevent out-of-bounds errors.
In the string, ‘0’ represents white, ‘1’ represents black; character comparison should be used instead of numerical comparison.

This problem may seem a bit complex, but it is actually a relatively straightforward simulation problem, mainly testing attention to detail and coding implementation ability. As long as you carefully check each position’s submatrix against the conditions as required by the problem, you can solve it.

Example Code

#include <iostream>
#include <string>

// Store the input grid, each string represents a row, '0' represents white, '1' represents black
std::string str_ary[105];

/**
 * Check if the 4x4 submatrix starting from (x,y) meets the problem requirements
 * @param x The row coordinate of the top-left corner of the submatrix
 * @param y The column coordinate of the top-left corner of the submatrix
 * @param n Total number of rows in the grid
 * @param m Total number of columns in the grid
 * @return Whether it meets the requirements
 */
bool check(int x, int y, int n, int m) {
    // First check for out-of-bounds
    if (x + 4 > n || y + 4 > m) {
        return false;
    }
    
    // Traverse each position of the 4x4 submatrix
    for (int i = x; i < x + 4; i++) {
        for (int j = y; j < y + 4; j++) {
            // Check if the first and last rows are all white (0)
            if (i == x || i == x + 3) {
                if (str_ary[i][j] != '0') {
                    return false;
                }
            }
            
            // Check if the first and last rows' first and last columns are white (0)
            if (j == y || j == y + 3) {
                if (str_ary[i][j] != '0') {
                    return false;
                }
            }
            
            // Check if the middle two columns of the second and third rows are black (1)
            if ((i == x + 1 || i == x + 2) && (j == y + 1 || j == y + 2)) {
                if (str_ary[i][j] != '1') {
                    return false;
                }
            }
        }
    }
    return true;
}

int main() {
    // Read the number of test cases
    int t;
    std::cin >> t;
    
    // Process each test case
    while (t--) {
        // Read the number of rows and columns in the grid
        int n, m;
        std::cin >> n >> m;
        
        // Read the grid data
        for (int i = 0; i < n; i++) {
            std::cin >> str_ary[i];
        }
        
        // Flag to mark if a satisfying submatrix is found
        bool flag = false;
        
        // Enumerate all possible top-left starting points
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // Check if the 4x4 submatrix with (i,j) as the top-left corner meets the requirements
                if (check(i, j, n, m)) {
                    std::cout << "Yes" << std::endl;
                    flag = true;
                    break;
                }
            }
            if (flag) {
                break;
            }
        }
        
        // If no satisfying submatrix is found, output No
        if (!flag) {
            std::cout << "No" << std::endl;
        }
    }
    return 0;
}

For GESP syllabus, real exam explanations, knowledge expansion, and practice lists, see:

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

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

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