USACO 2021 January Contest, Platinum

Problem 3. Paint by Letters


Contest has ended.

Log in to allow submissions in analysis mode


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 并没有真正进行任何的涂色，所以对于每个候选的回答是独立的。

注意：本题每个测试点的时间限制为默认限制的 1.5 倍，且内存限制为默认限制的 2 倍，为 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$，但如果仅考虑子矩形内的方格则并非如此。

测试点性质：

  • 测试点 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 中，每个由相同期望颜色的方格组成的连通分量均能够被一个四边平行于坐标轴的两行两列的正方形所包含。问题描述中的 $3\times 3$ 画布不符合这一性质（由五个 B 组成的连通分量不能被一个两行两列的正方形包含）。
  • 测试点 9-11 中，每个由相同期望颜色的方格组成的连通分量均能够被一个四边平行于坐标轴的三行三列的正方形所包含。问题描述中的 $3\times 3$ 画布符合这一性质。
  • 测试点 12-20 没有额外限制。

供题：Andi Qu

Contest has ended. No further submissions allowed.