题解：恼人的绘画工具（Annoying Painting Tool）

一、题目分析

本题要求通过若干次矩形区域翻转操作，将全白的图像转换为目标图像。每次操作可翻转一个 r×c 矩形内的所有像素颜色（0变1，1变0）。核心问题是判断是否可行，并求最小操作次数。

二、核心思路

1. 贪心策略：
   从左上角开始逐行逐列处理像素。若当前像素 mat[i][j] 为1，必须在此处执行一次翻转操作（因为后续无法影响该像素）。通过这种方式确保每个需要翻转的位置只处理一次，避免重复计算。

2. 操作顺序：
   仅处理可以完整容纳 r×c 矩形的区域（即 i+r ≤ n 且 j+c ≤ m）。对于超出该范围的像素，若仍为1，则无法通过任何操作翻转，直接判定不可行。

3. 状态更新：
   每次翻转操作后，更新该矩形内所有像素的状态，确保后续处理基于最新状态。

三、代码解析

#include <cstdio>
#include <cstring>
using namespace std;

bool mat[105][105]; // 存储图像状态（0为白，1为黑）

int main() {
    int n, m, r, c;
    while (~scanf("%d%d%d%d", &n, &m, &r, &c) && (n || m || r || c)) {
        // 读取目标图像
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char t;
                scanf(" %c", &t);
                mat[i][j] = t - '0'; // 转换为布尔值
            }
        }

        int op = 0; // 操作次数
        bool ok = true;

        // 逐行逐列处理可操作区域
        for (int i = 0; i + r <= n; i++) {
            for (int j = 0; j + c <= m; j++) {
                if (mat[i][j]) { // 当前像素为黑，需要翻转
                    op++;
                    // 翻转r×c矩形内的所有像素
                    for (int x = i; x < i + r; x++) {
                        for (int y = j; y < j + c; y++) {
                            mat[x][y] = !mat[x][y]; // 取反
                        }
                    }
                }
            }
        }

        // 检查剩余像素是否全为白
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j]) {
                    ok = false;
                    break;
                }
            }
            if (!ok) break;
        }

        printf("%d\n", ok ? op : -1); // 输出结果
    }
    return 0;
}

四、步骤详解

1. 输入处理：
   读取图像尺寸 n×m 和操作矩形尺寸 r×c，以及目标图像的每个像素值，存储为布尔矩阵 mat。

2. 贪心翻转：
   遍历所有可以执行 r×c 翻转的左上角坐标 (i, j)：

   • 若当前像素 mat[i][j] 为1，执行翻转操作，操作次数 op 加1。
   • 翻转该矩形内的所有像素（通过取反实现）。

3. 可行性检查：
   处理完所有可操作区域后，检查剩余像素是否全为0（白色）。若存在1，则无法完成目标，输出-1；否则输出操作次数 op。

五、关键点总结

1. 贪心的正确性：
   从左上到右下处理，确保每个需要翻转的位置在其左上角可操作时处理，避免后续无法影响该位置。这种策略保证了最小操作次数。

2. 不可行条件：
   当处理完所有可操作区域后，若右下角 (n-r+1 ≤ i < n, m-c+1 ≤ j < m) 的像素仍为1，则无法通过任何操作翻转，直接判定不可行。

3. 时间复杂度：
   每次翻转操作的时间为 O(r×c)，总共有 O((n-r+1)(m-c+1)) 次可能的操作，整体复杂度为 O(nmrc)，对于 n,m≤100 的规模完全可行。

六、常见错误处理

• 边界条件：确保循环范围为 i + r ≤ n 和 j + c ≤ m，避免越界操作。
• 状态更新：每次翻转后及时更新像素状态，确保后续操作基于正确的当前状态。

该解法通过贪心策略和逐行逐列处理，高效地解决了图像翻转问题，确保在最短操作次数内完成目标或正确判断不可行性。