Paint by Letters

题目描述

Bessie 最近收到了一套绘画工具。画布可以表示为一个 $N \times M$ 的矩形网格，行从上到下标号为 $1\ldots N$，列从左到右标号为 $1\ldots M$（$1\le N,M\le 1000$）。涂色后，每个格子的颜色可以用从 'A' 到 'Z' 的大写字母表示。初始时所有格子都未上色，并且一个格子不能被涂色超过一次。 Bessie 为每个格子指定了她想要的颜色。如果一组格子构成一个连通块，她就可以用一次笔画将这组格子涂成同一种颜色；这里的连通块指的是：集合中任意一个格子都可以通过一系列相邻格子到达集合中的任意另一个格子。若两个格子共享一条边，则认为它们相邻。 例如，对于如下 $3\times 3$ 画布 AAB BBA BBB 可以用四次笔画完成涂色，如下所示： ... ..B AAB AAB AAB ... -> ... -> ... -> BB. -> BBA ... ... ... BBB BBB 不可能用少于四次笔画得到最终结果。 作为一名先锋艺术家，Bessie 最终只会涂画布的某个子矩形区域。目前她正在考虑 $Q$ 个候选（$1\le Q\le 1000$），每个候选由四个整数 $x_1$、$y_1$、$x_2$、$y_2$ 表示。这意味着该子矩形包含所有满足行号在 $x_1$ 到 $x_2$（含端点）之间、列号在 $y_1$ 到 $y_2$（含端点）之间的格子。 对于每个候选子矩形，要求在保持子矩形外所有格子仍未上色的前提下，将子矩形内每个格子涂成其期望颜色所需的最少笔画数是多少？注意 Bessie 并不会真的进行涂色，因此每个候选的答案彼此独立。 注意：本题时间限制比默认值高 50%，内存限制为 512MB，是默认值的两倍。

输入格式

第一行包含 $N$、$M$ 和 $Q$。 接下来 $N$ 行，每行包含一个长度为 $M$ 的大写字母字符串，表示画布每一行的期望颜色。 接下来 $Q$ 行，每行包含四个用空格分隔的整数 $x_1,y_1,x_2,y_2$，表示一个候选子矩形（$1\le x_1\le x_2\le N$，$1\le y_1\le y_2\le M$）。

输出格式

对于每个 $Q$ 个候选子矩形，输出答案，每行一个。

4 8 9
ABBAAAAA
ABAAAABA
CAADABBA
AAAAAAAA
1 1 4 8
3 5 3 8
1 3 2 4
1 4 2 5
1 1 3 3
4 4 4 4
2 6 4 8
3 5 4 6
1 6 3 8

6
3
2
1
4
1
3
2
2

提示

第一个候选是整个画布，可以用六次笔画完成涂色。 第二个候选是期望颜色为 ABBA 的子矩形，可以用三次笔画完成。注意，虽然在考虑整个画布时，位于 $(3,5)$ 和 $(3,8)$ 的格子可以在一次笔画中用 $A$ 涂色，但当只考虑该子矩形内的格子时则不成立。 SCORING: 测试点 1-2 满足 $N,M\le 50$。 在测试点 3-5 中，画布中不存在单一颜色的环。也就是说，不存在一列互不相同的格子 $c_1,c_2,c_3,\ldots,c_k$ 使得以下所有条件同时成立： $k>2$ $c_1,\ldots,c_k$ 的期望颜色都相同。 对每个 $1\le i<k$，$c_i$ 与 $c_{i+1}$ 相邻。 $c_k$ 与 $c_1$ 相邻。 注意，上面的 $3\times 3$ 画布包含一个单一颜色的环（左下角的四个 B）。 在测试点 6-8 中，每个由相同期望颜色的格子组成的连通块都可以包含在一个边与坐标轴平行的 $2\times 2$ 正方形内。上面的 $3\times 3$ 画布不满足该性质（由五个 B 组成的连通块无法包含在一个 $2\times 2$ 正方形内）。 在测试点 9-11 中，每个由相同期望颜色的格子组成的连通块都可以包含在一个边与坐标轴平行的 $3\times 3$ 正方形内。上面的 $3\times 3$ 画布满足该性质。 测试点 12-20 没有额外限制。 题目来源：Andi Qu

标签: USACO|2021|Platinum

来源

USACO|2021|Platinum