Astral Superposition

题目描述

注意：本题时间限制为 4s，是默认时间限制的两倍。 Bessie 正在用她精巧的望远镜拍摄夜空中的所有星星。她的望远镜可以拍摄一张 $N \times N$ 的照片（$1 \leq N \leq 1000$），其中每个像素要么是星星，要么是空的天空。每颗星星恰好由一个像素表示，并且任意两颗不同的星星不会占据同一个像素。

一夜之间，天空中的星星发生了奇怪的变化。每颗星星要么消失，要么向右移动 $A$ 个像素、向下移动 $B$ 个像素（$0 \leq A,B \leq N$）。如果一颗星星消失或移动到了照片边界之外，那么它就不会出现在第二张照片中。

Bessie 在星星位置变化前后各拍了一张照片，但在 Mootoshop 里实验时不小心把两张照片叠加在了一起。现在，她看到：两张照片都为空的像素是白色；恰好只有一张照片中有星星的像素是灰色；两张照片中都有星星的像素是黑色。Bessie 还记得，第二张照片的画面中不会有新的星星从外面移入，因此第一张照片包含了夜空中的所有星星。

给定最终叠加后的照片，对于 $T$（$1 \leq T \leq 1000$）个相互独立的测试用例，求在变化发生前夜空中星星的最小可能数量。若不存在任何星星排列能够产生给定的最终照片，则输出 $-1$。

输入格式

第一行输入包含 $T$，随后给出 $T$ 个测试用例。

每个测试用例的第一行包含 $N$ $A$ $B$。 接下来是 $N$ 行，每行表示叠加照片的一行。从上往下第 $i$ 行用字符串 $c_{i,1}c_{i,2}\dots c_{i,N}$ 表示，其中每个 $c_{i,j} \in \{W,G,B\}$，分别表示白色、灰色和黑色。

保证所有测试用例的 $N^2$ 之和不超过 $10^7$。

输出格式

对于每个测试用例，输出变化发生前星星数量的最小值；若不可能则输出 $-1$。

1
3 0 0
WWB
BBB
GGG

7

3
5 1 2
GWGWW
WGWWW
WBWGW
WWWWW
WWGWW
3 1 1
WWW
WBW
WWW
3 1 0
GGB
GGW
WWW

4
-1
4

提示

在这个例子中，没有发生位移。第一张照片如下所示：（. 表示天空，* 表示星星） ..*

---

---

第二张照片中，底部一行的星星消失了，照片如下所示： ..*

---

... 这是产生该叠加照片的唯一方式，因此初始星星数量的最小可能值为 $7$。

在第一个用例中，起初至少有 $4$ 颗星星。若用 $(r,c)$ 表示从上往下第 $r$ 行与从左往右第 $c$ 列的交点，一种可能是它们最初在 $(1,1), (3,2), (2,2),$ 以及 $(1,3)$。所有星星都发生了位移，除了位于 $(2,2)$ 的那颗消失了。 在第二个用例中，不存在任何初始照片中的星星排列能够在给定位移下产生中间的黑色像素。 在第三个用例中，起初至少有 $4$ 颗星星。一种可能是它们最初在 $(1,1), (1,2), (1,3),$ 以及 $(2,1)$。在第二张照片中，原本在 $(1,1)$ 的星星消失了，原本在 $(1,3)$ 的星星移出了画面。其余两颗向右移动了 1。

SCORING: Input 3: $A=B=0$ Inputs 4-7: $A=1, B=0, N\le 10$ Inputs 8-9: $A=1, B=0$ Inputs 10-12: No additional constraints. Problem credits: Suhas Nagar

标签: USACO|2025|Bronze

来源

USACO|2025|Bronze