题意理解 我们有一个 N × M N×M 的网格，每个格子有一个目标颜色（大写字母）。

Bessie 一笔可以涂一个连通分量（四连通），要求这一笔涂的所有格子颜色相同。

给定 Q Q 个矩形区域，对每个矩形，问最少需要多少笔才能把矩形内部所有格子涂成目标颜色（矩形外部不涂）。

N , M ≤ 1000 N,M≤1000

Q ≤ 1000 Q≤1000

初步分析 对于单个矩形，我们可以把它看作一个子网格图，每个格子是一个顶点，相邻且颜色相同的格子之间连一条边。

那么最少笔数 = 该子矩形中颜色相同连通分量的数量。

但是注意：即使两个格子颜色相同，如果它们在子矩形中不连通（因为路径必须完全在子矩形内），那么它们需要分开涂。

所以问题转化为： 对于矩形区域，计算颜色相同且四连通的连通块个数。

直接做法与复杂度 对每个查询，在矩形内做 BFS/DFS 找连通块，复杂度 O ( Q ⋅ N M ) O(Q⋅NM)，太大（ 10 9 10 9 级别）。

需要预处理。

平面图与欧拉公式 这是一个平面图问题： 我们把每个格子看作一个面（face），相邻且同色的格子属于同一个面。

更准确地说： 我们构造一个图 G G：

顶点 = 每个格子

边 = 相邻且同色的格子之间的边

那么每个连通分量是一个面（在子矩形中可能被切断）。

欧拉公式 对于一个平面连通图：

V − E + F

1 + C V−E+F=1+C 其中：

V V = 顶点数

E E = 边数

F F = 面数（包括外面）

C C = 连通分量数

但我们这里不是对整个图，而是对子矩形。

关键思路 对于子矩形 R R，定义：

V V = 矩形内格子数

E E = 矩形内相邻且同色的边数（边两端都在矩形内）

C C = 矩形内连通块数（我们要求的答案）

但是直接套欧拉公式不行，因为子矩形不是整个平面图。

对偶图方法 考虑构造对偶图：

原图的顶点 = 格子中心

原图的边 = 相邻格子之间的边（如果同色则边存在，否则不存在）

我们要求的是原图在子矩形中的连通分量数。

利用边界和环 一个已知结论（类似 USACO 官方题解）： 对于子矩形，定义：

V V = 格子数

E E = 内部同色边数

B B = 与矩形外部相邻的边数（即矩形边界上的边，且该边连接的两个格子颜色不同）

H H = 矩形内部“洞”的数量（即被矩形包围但颜色不同的区域形成的环）

那么：

C

V − E + H + B 2 ? C=V−E+H+ 2 B ​ ? 实际上更准确的是：

官方解法思路 定义：

对每个格子，它是一个面。

相邻且同色的格子属于同一个面。

在子矩形中，一个“笔划”对应一个同色连通分量。

我们构造对偶图：

顶点 = 每个格子中心

边 = 相邻格子之间的边（如果同色则边存在，否则不存在）

那么子矩形中的连通分量数 = 顶点数 - 边数 + 环数 + 边界调整项。

更精确公式（经过推导）：

笔数

( 顶点数 ) − ( 内部边数 ) + ( 边界上的连通块数 ) 笔数=(顶点数)−(内部边数)+(边界上的连通块数) 其中“边界上的连通块数”指在矩形边界上，相邻且同色的格子形成的连通块数。

高效计算 我们可以预处理：

V[x1,y1,x2,y2] = 矩形内格子数 = (x2-x1+1)*(y2-y1+1)

E[x1,y1,x2,y2] = 矩形内相邻且同色的边数（水平+垂直）

B[x1,y1,x2,y2] = 矩形边界上同色连通块数

那么：

答案

V − E + B 答案=V−E+B 预处理 E E 可以分成水平边和垂直边：

水平边：对每行 i，列 j 从 1 到 M-1，如果 grid[i][j] == grid[i][j+1]，则存在一条水平边 (i,j)-(i,j+1)。

我们可以用二维前缀和 hor[i][j] 表示从 (1,1) 到 (i,j) 的水平边数。

类似地，垂直边：对每列 j，行 i 从 1 到 N-1，如果 grid[i][j] == grid[i+1][j]，则存在一条垂直边 (i,j)-(i+1,j)。

用二维前缀和 ver[i][j] 表示从 (1,1) 到 (i,j) 的垂直边数。

那么矩形 (x1,y1,x2,y2) 内的边数 =

水平边：hor[x2][y2-1] - hor[x1-1][y2-1] - hor[x2][y1-1] + hor[x1-1][y1-1]（注意 y2-1 因为水平边在 j 和 j+1 之间）

垂直边：ver[x2-1][y2] - ver[x1-1][y2] - ver[x2-1][y1-1] + ver[x1-1][y1-1]（注意 x2-1 因为垂直边在 i 和 i+1 之间）

预处理 B 边界上的连通块数 = 上边界 + 下边界 + 左边界 + 右边界 - 四个角重复计算。

我们可以对每个边界单独计算连通块数，然后减去角上重复的。

具体：

上边界：行 x1，列 y1..y2

下边界：行 x2，列 y1..y2

左边界：列 y1，行 x1..x2

右边界：列 y2，行 x1..x2

对每个边界，数一下颜色变化的次数（相邻格子颜色不同则断开），连通块数 = 变化次数 + 1。

然后减去四个角，因为角在两条边界都被算了一次。

算法步骤 读入 N, M, Q 和网格

预处理水平边前缀和 hor 和垂直边前缀和 ver

对每个查询 (x1,y1,x2,y2)：

V = (x2-x1+1)*(y2-y1+1)

E = 水平边数 + 垂直边数（用前缀和计算）

B = 边界连通块数（单独计算四条边，减角）

答案 = V - E + B

边界连通块数计算 以上边界为例：

cpp int top = 1; for (int j = y1+1; j <= y2; j++) { if (grid[x1][j] != grid[x1][j-1]) top++; } 类似计算 bottom, left, right。

然后：

cpp B = top + bottom + left + right; // 减去四个角重复 if (grid[x1][y1] != grid[x1][y1+1] && grid[x1][y1] != grid[x1+1][y1]) B--; // 其他三个角类似 实际上更简单：每个角如果与相邻两边颜色都不同，则它在两条边界上都被算作新块，多算了一次，所以要减 1。

复杂度 预处理 O(NM)

每个查询 O(N+M)（因为要遍历边界）

总 O(NM + Q(N+M))，可接受（约 2×10^6）

代码框架 cpp #include <bits/stdc++.h> using namespace std;

int N, M, Q; vector grid; vector<vector> hor, ver;

int main() { cin >> N >> M >> Q; grid.resize(N+1); for (int i = 1; i <= N; i++) { string s; cin >> s; grid[i] = " " + s; }

// 预处理水平边前缀和
hor.assign(N+1, vector<int>(M+1, 0));
for (int i = 1; i <= N; i++) {
    for (int j = 1; j < M; j++) {
        hor[i][j] = hor[i-1][j] + hor[i][j-1] - hor[i-1][j-1];
        if (grid[i][j] == grid[i][j+1]) hor[i][j]++;
    }
    hor[i][M] = hor[i][M-1]; // 扩展最后一列
}

// 预处理垂直边前缀和
ver.assign(N+1, vector<int>(M+1, 0));
for (int j = 1; j <= M; j++) {
    for (int i = 1; i < N; i++) {
        ver[i][j] = ver[i-1][j] + ver[i][j-1] - ver[i-1][j-1];
        if (grid[i][j] == grid[i+1][j]) ver[i][j]++;
    }
    ver[N][j] = ver[N-1][j]; // 扩展最后一行
}

while (Q--) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    
    int V = (x2 - x1 + 1) * (y2 - y1 + 1);
    
    // 计算 E
    int E = 0;
    // 水平边
    if (y2 > y1) {
        E += hor[x2][y2-1] - hor[x1-1][y2-1] - hor[x2][y1-1] + hor[x1-1][y1-1];
    }
    // 垂直边
    if (x2 > x1) {
        E += ver[x2-1][y2] - ver[x1-1][y2] - ver[x2-1][y1-1] + ver[x1-1][y1-1];
    }
    
    // 计算边界连通块数 B
    int B = 0;
    // 上边界
    int top = 1;
    for (int j = y1+1; j <= y2; j++) {
        if (grid[x1][j] != grid[x1][j-1]) top++;
    }
    // 下边界
    int bottom = 1;
    for (int j = y1+1; j <= y2; j++) {
        if (grid[x2][j] != grid[x2][j-1]) bottom++;
    }
    // 左边界
    int left = 1;
    for (int i = x1+1; i <= x2; i++) {
        if (grid[i][y1] != grid[i-1][y1]) left++;
    }
    // 右边界
    int right = 1;
    for (int i = x1+1; i <= x2; i++) {
        if (grid[i][y2] != grid[i-1][y2]) right++;
    }
    
    B = top + bottom + left + right;
    
    // 减去四个角重复
    // 左上角
    if (x1 > 0 && y1 > 0 && grid[x1][y1] != grid[x1][y1+1] && grid[x1][y1] != grid[x1+1][y1]) B--;
    // 右上角
    if (x1 > 0 && y2 < M && grid[x1][y2] != grid[x1][y2-1] && grid[x1][y2] != grid[x1+1][y2]) B--;
    // 左下角
    if (x2 < N && y1 > 0 && grid[x2][y1] != grid[x2][y1+1] && grid[x2][y1] != grid[x2-1][y1]) B--;
    // 右下角
    if (x2 < N && y2 < M && grid[x2][y2] != grid[x2][y2-1] && grid[x2][y2] != grid[x2-1][y2]) B--;
    
    int ans = V - E + B;
    cout << ans << "\n";
}

return 0;

} 总结 这道题的核心是：

将最少笔数问题转化为子矩形内同色连通块计数

利用平面图性质得到公式：笔数 = 顶点数 - 边数 + 边界连通块数

用二维前缀和预处理边数

对每个查询扫描边界计算边界连通块数

这样就能在 O ( N M + Q ( N + M ) ) O(NM+Q(N+M)) 时间内解决。