Counting Black（网格涂色与查询）题解

题目分析

本题要求对一个$100 \times 100$的网格进行动态操作与查询，包含三种操作类型：

• 涂白（WHITE）：将指定左上角坐标$(x,y)$、边长为$L$的矩形区域内的所有网格涂为白色。
• 涂黑（BLACK）：将指定左上角坐标$(x,y)$、边长为$L$的矩形区域内的所有网格涂为黑色。
• 查询（TEST）：统计指定左上角坐标$(x,y)$、边长为$L$的矩形区域内黑色网格的数量。

初始时所有网格为白色，需根据输入命令动态更新网格状态，并在查询时返回结果。

方法思路

本题采用 直接模拟法，核心思想是通过二维数组直接表示网格状态，逐操作更新并统计。具体思路如下：

1. 网格状态表示

使用一个二维数组$table$（大小$101 \times 101$，下标从$1$开始）表示网格，其中：

• $table[row][col] = 1$：表示$(row, col)$位置的网格为黑色。
• $table[row][col] = 0$：表示$(row, col)$位置的网格为白色。

2. 操作实现逻辑

• 涂白操作：遍历指定矩形区域内的所有网格，将其值置为$0$。
• 涂黑操作：遍历指定矩形区域内的所有网格，将其值置为$1$。
• 查询操作：遍历指定矩形区域内的所有网格，统计值为$1$的网格数量。

3. 复杂度分析

• 单次涂白/涂黑操作的时间复杂度为$O(L^2)$（$L$为矩形边长，最大$100$）。
• 单次查询操作的时间复杂度同样为$O(L^2)$。
• 由于命令总数$t \leq 100$，总操作次数为$100 \times 100^2 = 10^6$，在时间限制内完全可行。

解决代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int table[101][101]; // 网格数组，下标从1开始（对应题目坐标）

// 涂白操作：将(x, y)为左上角、边长L的矩形区域置为白色（0）
void white(int x, int y, int L) {
    for (int row = x; row <= x + L - 1; row++) {
        for (int col = y; col <= y + L - 1; col++) {
            table[row][col] = 0;
        }
    }
}

// 涂黑操作：将(x, y)为左上角、边长L的矩形区域置为黑色（1）
void black(int x, int y, int L) {
    for (int row = x; row <= x + L - 1; row++) {
        for (int col = y; col <= y + L - 1; col++) {
            table[row][col] = 1;
        }
    }
}

// 查询操作：统计(x, y)为左上角、边长L的矩形区域内的黑色网格数
int test(int x, int y, int L) {
    int count = 0;
    for (int row = x; row <= x + L - 1; row++) {
        for (int col = y; col <= y + L - 1; col++) {
            if (table[row][col] == 1) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int n;
    char cmd[8]; // 存储命令类型（WHITE/BLACK/TEST）
    int x, y, L;

    memset(table, 0, sizeof(table)); // 初始化全为白色（0）
    scanf("%d", &n);

    while (n--) {
        scanf("%s%d%d%d", cmd, &x, &y, &L);
        if (strcmp(cmd, "WHITE") == 0) {
            white(x, y, L);
        } else if (strcmp(cmd, "BLACK") == 0) {
            black(x, y, L);
        } else { // TEST命令
            printf("%d\n", test(x, y, L));
        }
    }

    return 0;
}

代码解释

1. 数据结构设计：
   使用二维数组$table[101][101]$存储网格状态，下标从$1$开始，与题目中坐标$(1,1)$到$(100,100)$直接对应，避免越界问题。

2. 核心函数说明：

   • $white$函数：接收左上角坐标$(x,y)$和边长$L$，通过双重循环遍历区域内所有网格（行从$x$到$x+L-1$，列从$y$到$y+L-1$），将每个网格置为$0$（白色）。
   • $black$函数：逻辑与$white$函数类似，遍历区域内网格并置为$1$（黑色）。
   • $test$函数：遍历指定区域内的网格，逐个检查是否为黑色（值为$1$），统计总数后返回。

3. 主函数流程：

   • 初始化：使用$memset$将$table$数组全部置$0$（初始全白）。
   • 读取命令：循环读取$n$条命令，每条命令包含类型（$cmd$）、坐标$(x,y)$和边长$L$。
   • 命令处理：根据$cmd$类型调用$white$、$black$或$test$函数，查询结果直接输出。

优化说明

本题网格规模较小（$100 \times 100$），直接遍历每个操作涉及的网格是最简洁有效的方法。若网格规模扩大（如$1000 \times 1000$），可引入二维前缀和数组优化查询操作（预处理前缀和，查询时$O(1)$计算区域和），但本题数据范围下直接模拟已足够高效。